概要

与えられた会議のうち、時間帯が重ならないように最大何個選べるかを求める問題です。

考察

この問題は典型的な「区間スケジューリング問題」として知られています。目標は、重ならない区間をできるだけ多く選ぶことです。

まず、素朴な方法として「すべての組み合わせを試す」ことが考えられますが、会議の数 \(N\) は最大で \(2 \times 10^5\) なので、全探索は現実的ではありません（計算量は指数時間）。

重要な観察は、「終了時刻が早い会議を選ぶほど、その後により多くの会議を入れる余地ができる」という点です。つまり、貪欲法（Greedy Algorithm）が有効です。

具体的には： - 各会議を「終了時刻」の早い順にソートします。 - ソート後に前から見ていき、「直前に選んだ会議の終了時刻」以降に始まる会議を選んでいけば良いです。

この貪欲戦略が最適解を与える理由は、終了時刻が早いものを選ぶことで、残り時間に他の会議を詰め込む柔軟性が増すためです。

例えば以下のような入力の場合：

終了時刻でソートすると A → C → B の順になります。A を選び、次に C が選べるので、最大数は 2 です。

一方で、開始時刻が早い順に選ぶと A → B となり、2つしか選べませんが、これは誤りです。

アルゴリズム

1. すべての会議を \((L_i, R_i)\) の形でリストに格納する。
2. 会議を「終了時刻 \(R_i\)」の昇順でソートする。
3. 最初の会議を選択し、その終了時刻を記録する。
4. 次の会議から順に見て行き、その会議の開始時刻が「最後に選んだ会議の終了時刻以上」であれば選ぶ。
5. 選んだ会議数を出力する。

計算量

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

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。
• 区間の比較は (L, R) のペアで扱い、ソートキーに lambda x: x[1]（終了時刻）を指定している。
• 前の会議の終了時刻を変数 last_end で管理し、現在の会議の開始時刻と比較することで重なりを判定している。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    meetings = []
    index = 1
    for _ in range(N):
        L = int(data[index])
        R = int(data[index+1])
        meetings.append((L, R))
        index += 2
    
    # 終了時刻でソートする
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end = -1
    
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
            
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。