概要

会議室の予約申請から、時間が重ならないように選べる会議の最大数を求める問題です。

考察

この問題は、区間スケジューリング問題として知られる典型的な問題です。素朴なアプローチとして全ての組み合わせを試す方法がありますが、\(N\)が最大20万件もあるため、\(O(2^N)\)の全探索は現実的ではありません。

重要な観察は、「終了時刻が早い会議から順に選択していく」という貪欲法が最適解を与えることです。なぜなら、終了時刻が早い会議を選ぶことで、後により多くの会議を入れられる可能性が高まるからです。

アルゴリズム

1. 全ての会議を終了時刻 \(R_i\) で昇順にソートする
2. 現在の終了時刻を-1（最初の会議が必ず選べるように）で初期化
3. ソートされた会議を順に処理する:
   • 現在の会議の開始時刻 \(L_i\) が現在の終了時刻以上なら
   • この会議を採用し、カウントを増やす
   • 現在の終了時刻をこの会議の終了時刻 \(R_i\) に更新する
4. 採用した会議の数を出力する

例えば、会議が [(1,3), (2,4), (3,5)] の場合、終了時刻でソートすると同じ順序になります。最初に(1,3)を採用、次に(2,4)は開始時刻2が現在の終了時刻3より小さいので採用せず、(3,5)は開始時刻3が現在の終了時刻3以上なので採用します。結果として2つの会議を選べます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートの計算量が支配的）
• 空間計算量: \(O(N)\)（会議データを格納するための配列）

実装のポイント

• ソートを効率的に行うために、終了時刻をタプルの最初の要素にすることで終了時刻でのソートが簡単になります

• 現在の終了時刻の初期値は-1にすることで、最初の会議が必ず選ばれるようになります

• 整数で入力を受け取るため、split()でデータを読み取っています

  ソースコード

import sys

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

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。