概要

\(N\) 件の会議の中から、時間帯が互いに重ならないように選べる会議の最大数を求める問題です。これは「区間スケジューリング問題」と呼ばれる有名な貪欲法の問題です。

考察

素朴なアプローチとその問題点

すべての会議の組み合わせを試して、互いに重ならない最大の部分集合を見つける方法が考えられます。しかし、\(N\) 件の会議の部分集合は \(2^N\) 通りあり、\(N\) が最大 \(2 \times 10^5\) なので、このアプローチは到底間に合いません。

重要な気づき：終了時刻が早い会議を優先する

直感的に考えてみましょう。会議室を「できるだけ早く空ける」ことができれば、その後により多くの会議を入れるチャンスが増えます。

例えば、以下の3つの会議があるとします：

会議	開始時刻	終了時刻
A	1	3
B	2	5
C	3	6

• 終了時刻が最も早い会議 A（終了時刻 3）をまず選びます。
• 次に、時刻 3 以降に開始する会議を探すと、会議 C（開始時刻 3）が選べます。
• 結果：A と C の 2 件 が最大です。

もし会議 B を最初に選んでいたら、残りの会議は選べず 1 件 にとどまります。このように、終了時刻が早い順に貪欲に選ぶことが最適であることが知られています。

アルゴリズム

この問題は区間スケジューリング問題と呼ばれ、以下の貪欲法で最適解が得られます。

1. すべての会議を終了時刻 \(R_i\) の昇順にソートする（終了時刻が同じ場合は開始時刻の昇順でよい）。
2. 変数 last_end（最後に選んだ会議の終了時刻）を \(-1\) で初期化する。
3. ソートした順に会議を見ていき、開始時刻 \(L_i \geq\) last_end であれば：
   • その会議を選び、count を \(1\) 増やす。
   • last_end を \(R_i\) に更新する。
4. 最終的な count が答え。

なぜこれが正しいのか？
終了時刻が早い会議を選ぶことで、残りの時間帯が最大限確保されます。この貪欲な選択が将来の選択肢を狭めないことが、交換論法（選ばなかった場合と選んだ場合を入れ替えても損しないことの証明）により保証されています。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（会議のリストを保持）

実装のポイント

• ソートのキーとして、タプル (R_i, L_i) を使うと、Python の標準ソートで終了時刻の昇順に自然にソートできます。コードでは meetings.append((r, l)) としてタプルの第1要素を終了時刻にすることで、meetings.sort() だけでソートが完了します。

• 会議が重ならない条件は \(L_i \geq\) last_end（前の会議の終了時刻以上に開始）です。問題文にある通り、終了時刻と開始時刻が一致する場合（\(R_i = L_j\)）は重ならないので、不等号は >=（等号を含む）にします。

• sys.stdin.read() で入力を一括読み込みし、split() で分割する方法は、\(N\) が大きい場合に input() を繰り返すより高速です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    meetings = []
    idx = 1
    for i in range(n):
        l = int(input_data[idx])
        r = int(input_data[idx + 1])
        meetings.append((r, l))
        idx += 2
    meetings.sort()
    count = 0
    last_end = -1
    for r, l in meetings:
        if l >= last_end:
            count += 1
            last_end = r
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。