概要

1つの会議室において、時間が重ならないように会議を詰め込んだとき、最大でいくつの会議を実施できるかを求める問題です。これは「区間スケジューリング問題」と呼ばれる、貪欲法を用いる典型的な問題の1つです。

考察

この問題を解くにあたって、どのような基準で会議を選んでいけばよいかを考えます。

• 開始時刻 \(L_i\) が早い順に選ぶ： 開始が非常に早く、終了が非常に遅い会議（例：0時〜23時）が1つあるだけで、他の多くの短い会議ができなくなってしまう可能性があるため、不適切です。
• 会議の時間（\(R_i - L_i\)）が短い順に選ぶ： 短い会議であっても、それが2つの会議のちょうど中間の時間に位置している場合、その1つを選ぶことで前後の2つの会議を潰してしまう可能性があるため、不適切です。

最適な戦略は、「終了時刻 \(R_i\) が早い順に選ぶ」ことです。 会議を早く終わらせれば終わらせるほど、その後の時間帯に余裕ができ、より多くの会議を詰め込める可能性が高まるからです。この「その場での最善（最も早く終わるもの）を選び続ける」という手法を貪欲法と呼びます。

アルゴリズム

1. 各会議の情報を (終了時刻 \(R_i\), 開始時刻 \(L_i\)) というペアのリストとして保持します。
2. リストを終了時刻 \(R_i\) の昇順にソートします。
3. 「現在会議室が空く時刻」を保持する変数 current_end_time を \(0\) で初期化します。
4. ソートされた会議を1つずつ確認し、以下の操作を行います：
   • もし会議の開始時刻 \(L_i\) が current_end_time 以上であれば、その会議を採用します。
   • 採用した場合、会議の合計数を \(+1\) し、current_end_time をその会議の終了時刻 \(R_i\) に更新します。
5. 最終的な合計数を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 会議の情報の読み込みに \(O(N)\)、終了時刻によるソートに \(O(N \log N)\)、その後の走査に \(O(N)\) かかります。全体のボトルネックはソート部分です。
• 空間計算量: \(O(N)\)
  • \(N\) 件の会議情報をリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• ソートの工夫: Pythonの sort() メソッドは、タプルのリストをソートする際に「第1要素、第2要素…」の順で比較します。そのため、(終了時刻, 開始時刻) という順序でタプルを作っておくと、引数を指定せずにそのままソートするだけで目的の順序になります。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.read().split() などを用いて一括で入力を取得することで、実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 会議の数 N
    n = int(input_data[0])
    
    # 各会議を (終了時刻, 開始時刻) のタプルとしてリストに格納
    # 終了時刻でソートするため、終了時刻を第一要素にする
    meetings = []
    for i in range(n):
        l = int(input_data[2 * i + 1])
        r = int(input_data[2 * i + 2])
        meetings.append((r, l))
    
    # 終了時刻が早い順にソート（区間スケジューリング問題の最適解）
    meetings.sort()
    
    count = 0
    current_end_time = 0
    
    for r, l in meetings:
        # 現在の会議の開始時刻が、直前に選んだ会議の終了時刻以降であれば採用
        if l >= current_end_time:
            count += 1
            current_end_time = r
            
    # 最大の会議数を出力
    print(count)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。