概要

各会議予約を区間 \([S_i, E_i)\) とみなし、同時に重なっている区間数の最大値（混雑度）を求める問題です。

考察

ある時刻 \(t\) の同時利用数は「\(t\) を含む予約区間の本数」です。これを全時刻 \(0 \le t < T\) で調べて最大を取ればよいですが、\(T\) は最大 \(10^9\) なので、1分ごとに数えるような方法（例：長さ \(T\) の配列を作る、全時刻を走査する）は 時間・メモリともに不可能 です。

ここで重要な気づきは次の通りです。

• 同時利用数が変化するのは、予約の 開始時刻 と 終了時刻 の瞬間だけ。
• それ以外の時刻では同時利用数は一定。

したがって、全ての時刻を見る必要はなく、開始・終了の「イベント」だけを時刻順に処理すれば最大値が求まります。

また本問題は区間が 開始を含み、終了を含まない（\(S_i \le t < E_i\)）という半開区間です。
そのため、同じ時刻に「ある会議が終了」し「別の会議が開始」する場合、それらは同時利用として数えません。
つまり 同時刻なら終了イベントを先に処理 する必要があります（これを間違えると WA になります）。

例： - 予約A: \([1,3)\)、予約B: \([3,5)\) は時刻 3 で重なりません。 - もし「開始を先に」処理すると時刻 3 で一瞬 2 と数えてしまい誤りになります。

アルゴリズム

「イベントソート＋累積（スイープライン）」で解きます。

1. 各予約 \([S_i, E_i)\) についてイベントを2つ作る
   
   • \((S_i, +1)\)：開始なので同時利用数が 1 増える
     
   • \((E_i, -1)\)：終了なので同時利用数が 1 減る
2. 全イベントを時刻でソートする
   
   • 同時刻の場合は 終了(-1)を開始(+1)より先 に処理したい
     
   • コードでは (time, delta) の昇順でソートし、-1 < +1 を利用して実現している
3. ソートした順にイベントを処理し、現在の同時利用数 cur を更新する
   
   • cur += delta
   • ans = max(ans, cur) を更新

これで全時刻の最大同時利用数が求まります。

計算量

• 時間計算量: \(O(N \log N)\)（イベント数 \(2N\) をソート）
• 空間計算量: \(O(N)\)（イベント配列）

実装のポイント

• 半開区間 \([S, E)\) なので、同時刻の処理順は「終了→開始」が正しい
  

  • 本コードでは events.sort(key=lambda x: (x[0], x[1])) により、同時刻は -1 が先になります

• \(N \le 2 \times 10^5\) なのでイベントは最大 \(4 \times 10^5\) 個になり、入出力も含めて高速化が有効
  

  • sys.stdin.buffer.read() でまとめて読み込む実装になっています

• \(T\) は入力にありますが、この解法では「変化点のみを見る」ため直接は使いません（制約として \(S_i,E_i\) が \([0,T]\) に収まることを保証するための値です）

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, T = data[0], data[1]
    events = []
    idx = 2
    for _ in range(N):
        s = data[idx]
        e = data[idx + 1]
        idx += 2
        events.append((s, 1))
        events.append((e, -1))

    events.sort(key=lambda x: (x[0], x[1]))  # (-1) before (+1) at same time

    cur = 0
    ans = 0
    for _, d in events:
        cur += d
        if cur > ans:
            ans = cur

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。