概要

会議の時間区間が重ならないようにいくつか選び、実施できる会議数を最大化する問題です。終了時刻が早い会議から貪欲に選ぶことで最適解が得られます。

考察

この問題は典型的な「区間スケジューリング（活動選択問題）」です。

• 会議 \(i\) を区間 \((L_i, R_i)\) とみなし、重ならない条件は
  ある順に選んだとき「次に選ぶ会議の開始時刻 \(L\) が、直前に選んだ会議の終了時刻 \(R\) 以上（\(L \ge R\)）」であればOK、ということになります。
  ※ \(R_i = L_j\) は重ならないので、条件は \(L \ge \text{last\_end}\) になります。

• 素朴に「全探索で最大個数」をしようとすると、会議を選ぶ/選ばないの \(2^N\) 通りで到底間に合いません。
  また、DPを考えても時刻が最大 \(10^9\) なので「時刻を軸にしたDP」はできませんし、\(N=2\times 10^5\) では \(O(N^2)\) のDP（例えば“前に選べる会議を毎回線形探索”）もTLEになります。

• 重要な気づきは、早く終わる会議を先に選ぶほど、後ろに会議を詰め込みやすくなることです。
  例えば同じくらいの開始時刻なら、終了が早い方を選んだ方が次に選べる会議の候補が増えます。

この直感を厳密に使うと、「終了時刻の昇順に並べて、入れられるものを順に入れる」という貪欲法が最適になります。

アルゴリズム

1. すべての会議を終了時刻 \(R\) で昇順にソートする。
2. 変数 last_end を「最後に採用した会議の終了時刻」として持つ（初期値は十分小さくする）。
3. ソート順に会議 \((L, R)\) を見ていき、もし \(L \ge \text{last\_end}\) なら重ならないので採用し、
   • 採用数を \(+1\)
   • last_end = R に更新する
4. 最終的な採用数が答え。

なぜこれで最適か（直感的説明）

終了時刻が最も早い会議を選ぶと、それ以降の時間を最も多く残せます。
もし別の会議を選んで終了時刻が遅くなると、その分だけ後ろの会議を選べる可能性が減るため、最大数を達成しにくくなります。

計算量

• 時間計算量: ソートが支配的なので \(O(N \log N)\)
• 空間計算量: 区間の配列を持つため \(O(N)\)

実装のポイント

• 「重ならない」判定は \(L \ge \text{last\_end}\)（等号を含む）です。ここを \(L > \text{last\_end}\) にすると、\(R_i = L_j\) の連続会議を誤って弾いてWAになります。

• コードではソートしやすいように (R, L) の順で保存しています（Pythonのタプルは先頭要素から比較されるため）。

• last_end の初期値は入力の下限より十分小さければよく、コードでは -10**19 としています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    intervals = []
    for _ in range(N):
        L, R = map(int, input().split())
        intervals.append((R, L))
    intervals.sort()

    cnt = 0
    last_end = -10**19
    for R, L in intervals:
        if L >= last_end:
            cnt += 1
            last_end = R

    print(cnt)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。