概要

\(N\) 件の会議予約が与えられたとき、同時に行われている会議数の最大値（混雑度）を求める問題です。

考察

素朴なアプローチとその問題点

最も単純な方法は、時刻 \(0\) から \(T-1\) までの各時刻について、その時刻に開催中の会議数を数えることです。しかし、\(T\) が最大 \(10^9\) と非常に大きいため、\(O(T \times N)\) や \(O(T)\) のアプローチでは時間制限に間に合いません。

重要な気づき

同時利用数が変化するのは、会議が開始する時刻または会議が終了する時刻だけです。それ以外の時刻では同時利用数は変わりません。

例えば、3つの会議 \((0, 5), (2, 8), (4, 6)\) がある場合： - 時刻 0：1件目が開始 → 同時利用数 1 - 時刻 2：2件目が開始 → 同時利用数 2 - 時刻 4：3件目が開始 → 同時利用数 3（最大） - 時刻 5：1件目が終了 → 同時利用数 2 - 時刻 6：3件目が終了 → 同時利用数 1 - 時刻 8：2件目が終了 → 同時利用数 0

このように、注目すべき時刻は高々 \(2N\) 個しかありません。

アルゴリズム

イベントベースのスイープライン法を使用します。

1. イベントの記録: 各会議について、開始時刻に \(+1\)、終了時刻に \(-1\) を記録します。

   • 開始時刻 \(S_i\)：会議が1つ増える
   • 終了時刻 \(E_i\)：会議が1つ減る

2. 時刻でソート: すべてのイベント時刻を昇順にソートします。

3. 累積和で計算: ソートした順にイベントを処理し、累積和を取ることで各時刻での同時利用数を求めます。

4. 最大値を記録: 累積和の過程で最大値を更新していきます。

例: 会議 (0,5), (2,8), (4,6)

イベント: 時刻0で+1, 時刻2で+1, 時刻4で+1, 時刻5で-1, 時刻6で-1, 時刻8で-1

累積和:
時刻0: 0+1=1
時刻2: 1+1=2
時刻4: 2+1=3 ← 最大
時刻5: 3-1=2
時刻6: 2-1=1
時刻8: 1-1=0

答え: 3

計算量

• 時間計算量: \(O(N \log N)\)
  • イベントの記録: \(O(N)\)
  • 時刻のソート: \(O(N \log N)\)（最大 \(2N\) 個の時刻）
  • 累積和の計算: \(O(N)\)
• 空間計算量: \(O(N)\)
  • イベントを格納する辞書に最大 \(2N\) 個のエントリ

実装のポイント

1. defaultdict の活用: 同じ時刻に複数の開始・終了がある場合も、defaultdict(int) を使えば自然に加算できます。

2. 開始と終了の順序: 同じ時刻に開始と終了が重なる場合、この実装では同じキーに対して +1 と -1 が相殺されます。問題文では「終了時刻は含まない」とあるため、時刻 \(t\) で終了する会議と時刻 \(t\) で開始する会議は同時利用とはカウントされず、この実装で正しく処理されます。

3. 座標圧縮の効果: \(T\) が \(10^9\) と大きくても、実際に処理する時刻は \(2N\) 個以下なので、効率的に計算できます。

   ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    # イベントベースの座標圧縮アプローチ
    # 開始時刻で+1、終了時刻で-1として、累積和で同時利用数を計算
    events = defaultdict(int)
    
    for i in range(N):
        S = int(input_data[idx]); idx += 1
        E = int(input_data[idx]); idx += 1
        events[S] += 1
        events[E] -= 1
    
    # イベント時刻をソートして累積和を計算
    sorted_times = sorted(events.keys())
    
    max_count = 0
    current_count = 0
    
    for time in sorted_times:
        current_count += events[time]
        max_count = max(max_count, current_count)
    
    print(max_count)

solve()

この解説は claude4.5opus によって生成されました。