概要

与えられた \(N\) 件の会議のスケジュールから、同時に行われている会議の最大数を求め、必要な会議室の最小数を計算する問題です。

考察

この問題は、「同時に進行している会議の最大数はいくつか？」という問題に言い換えることができます。ある時刻において同時に行われている会議の数が、その時刻に必要となる会議室の数だからです。

素朴なアプローチとして、配列を用意して各時刻ごとに会議の数をカウントする方法（いもす法など）が考えられます。しかし、本問題では時刻の最大値が \(10^9\) と非常に大きいため、長さ \(10^9\) の配列を用意して各時刻を調べると、メモリ制限（MLE）や実行時間制限（TLE）に引っかかってしまいます。

これを解決するために、「会議が始まる瞬間」と「会議が終わる瞬間」だけに着目します。会議の状況が変化するのはこれらの時刻のみだからです。このように、変化の起きるタイミング（イベント）だけを抽出して時間順に処理する手法を イベントソート と呼びます。

アルゴリズム

1. イベントの作成: 各会議 \(i\) について、以下の2つのイベントを作成します。

   • 時刻 \(S_i\) に会議が始まるイベント（会議室の使用数が \(+1\) される）
   • 時刻 \(E_i\) に会議が終わるイベント（会議室の使用数が \(-1\) される） これらを (時刻, 増減値) というペアでリストに追加します。

2. イベントのソート: 作成した全イベントを「時刻の昇順」にソートします。 ここで重要なのは、同じ時刻に「開始」と「終了」が重なった場合の処理順序です。問題文には「ある会議の終了時刻と別の会議の開始時刻が一致する場合、それらは同じ会議室で連続して行うことができる」とあります。 つまり、同じ時刻であれば「終了（\(-1\)）」を「開始（\(+1\)）」よりも先に処理しなければ、一時的に会議室が余分に必要だと誤判定してしまいます。 ペアを (時刻, 増減値) としているため、同じ時刻なら増減値が小さい -1 が 1 よりも自然と前に並び、この条件を満たすことができます。

3. 最大値の計算: ソートされたイベントを順番に見ながら、現在使用中の会議室の数（増減値の累積和）を計算します。その過程で記録された使用数の 最大値 が、求める最小の会議室数となります。

計算量

• 時間計算量: \(O(N \log N)\)
  • イベントの数が \(2N\) 個であり、これらをソートするのに \(O(N \log N)\) の時間がかかります。ソート後の走査は \(O(N)\) で終わるため、全体の時間計算量は \(O(N \log N)\) となります。これは \(N = 2 \times 10^5\) の制約に対して十分に高速です。
• 空間計算量: \(O(N)\)
  • \(2N\) 個のイベントを配列（リスト）に保持するため、\(O(N)\) のメモリを使用します。

実装のポイント

イベントをソートする際、Pythonの sort() メソッドはタプルの1番目の要素（時刻）で比較し、同じ場合は2番目の要素（増減値）で比較します。 終了イベントを (E, -1)、開始イベントを (S, 1) としてリストに格納することで、特別な比較関数を書かなくても自動的に「同じ時刻なら終了が先」という正しい順序でソートされるのが、この実装の美しくてシンプルなポイントです。

ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    events = []
    
    idx = 1
    for _ in range(N):
        S = int(data[idx])
        E = int(data[idx+1])
        idx += 2
        events.append((S, 1))
        events.append((E, -1))
        
    events.sort(key=lambda x: (x[0], x[1]))
    
    ans = 0
    current = 0
    for _, val in events:
        current += val
        if current > ans:
            ans = current
            
    print(ans)

if __name__ == '__main__':
    main()

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