概要

複数の会議の開始時刻と終了時刻が与えられたとき、同時に開催されている会議の数の最大値（混雑度）を求めよ。

考察

この問題は典型的な「区間スケジューリング」や「イベント処理」の問題です。
愚直に考えると、すべての時刻 \(t\) に対して、その時刻に含まれる会議の数を数える必要があります。しかし、制約では \(T\) が最大 \(10^9\) まであり、すべての時刻を走査するのは現実的ではありません（時間計算量が \(O(TN)\) となりTLE）。

そこで、「イベントベースの処理」を考えます。つまり、会議の開始と終了をイベントとして扱い、それらを時刻順に処理していくことで、ある瞬間の同時利用数を動的に更新していきます。

注意点として、同じ時刻に開始と終了のイベントがある場合、終了を先に処理する必要があります。これは、終了と同時に次の会議が始まるようなケースで、カウントを正しく保つためです。

例えば、以下の2つの会議があったとします： - 会議A: [1, 3) - 会議B: [3, 5)

時刻3において、Aが終わりBが始まるので、同時利用数は1でなくてはいけません。もし開始を先に処理してしまうと、一時的に同時利用数が2になってしまうため、誤った結果になります。

アルゴリズム

1. 各会議の開始時刻 \(S_i\) に対応する「+1」イベントと、終了時刻 \(E_i\) に対応する「-1」イベントを作ります。
2. これらのイベントを時刻順にソートします。同じ時刻の場合は、終了イベント（-1）を開始イベント（+1）よりも先に処理します。
3. ソートされたイベントを前から見ていき、現在の同時利用数 current_overlap を更新していきます。
4. 更新するたびに、最大値 max_overlap を更新していきます。
5. 最後に max_overlap を出力します。

計算量

• 時間計算量: \(O(N \log N)\)（イベントのソートが支配的）
• 空間計算量: \(O(N)\)（イベントリストの保存）

実装のポイント

• 開始と終了のイベントをタプル (time, +1 or -1) としてまとめて管理する。

• ソートキーを (time, value) とすることで、同じ時刻でも終了イベントを先に処理できる。

• 入力を高速に読み込むために sys.stdin.read を使うと良い（特にPythonで大量の入力がある場合）。

  ソースコード

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    T = int(data[1])
    
    events = []
    for i in range(N):
        s = int(data[2 * i + 2])
        e = int(data[2 * i + 3])
        events.append((s, 1))   # 予約開始
        events.append((e, -1))  # 予約終了
    
    # イベントを時刻順にソート（同じ時刻なら終了イベントを先に処理）
    events.sort(key=lambda x: (x[0], x[1]))
    
    max_overlap = 0
    current_overlap = 0
    
    for time, change in events:
        current_overlap += change
        if current_overlap > max_overlap:
            max_overlap = current_overlap
    
    print(max_overlap)

if __name__ == "__main__":
    main()

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