概要

各会議の時間区間が重ならないように割り当てるとき、同時に進行している会議の最大数（＝必要な会議室数の最小値）を求める問題です。

考察

同じ会議室に入れられないのは「時間が重なる」会議同士なので、必要な会議室数は「ある時刻に同時に開催されている会議数」の最大値に等しくなります。
直感的には、同時に \(k\) 個の会議が走っている瞬間があれば会議室は最低でも \(k\) 室必要ですし、逆に常に同時開催数が \(k\) 以下なら \(k\) 室あれば順に割り当てられます。

素朴に「各会議を順に見て、使える部屋を探す」などを部屋リストを線形探索で行うと、最悪で \(O(N^2)\) になり \(N \le 2\times 10^5\) では間に合いません。

そこで「開始時刻」「終了時刻」を別々に並べ、時間の流れに沿って - 会議が始まったら同時開催数を \(+1\) - 会議が終わったら同時開催数を \(-1\) と更新し、その最大値を取ればよい、という考え方にします。

重要な注意として区間は半開区間 \([S_i, E_i)\) なので、終了時刻と開始時刻が同じなら重なりません。
つまり、\(S = E\) が同時に起きる場合は「終了を先に処理」する必要があります。コードでは条件を starts[i] < ends[j] とし、等しいときは終了（else 側）を先に進めることでこれを実現しています。

例：\((S,E)=(1,3),(3,5)\) は同じ部屋でOK
開始配列: \([1,3]\)、終了配列: \([3,5]\)
時刻3では starts[i] < ends[j] が成り立たないので終了を先に処理し、同時開催数が増えないようになります。

アルゴリズム

1. 全会議の開始時刻配列 starts と終了時刻配列 ends を作る。
2. starts と ends をそれぞれ昇順ソートする。
3. 2本のポインタ i（開始側）, j（終了側）を用意し、現在同時開催中の会議数 cur を管理する。
4. i < N の間、次に起きるイベントを比較する：
   • もし starts[i] < ends[j] なら次は「開始」なので cur += 1, i += 1
   • そうでなければ（starts[i] >= ends[j]）次は「終了」（同時刻なら終了優先）なので cur -= 1, j += 1
5. 途中での cur の最大値を答え ans として更新し、最終的に ans を出力する。

これは「時間軸上のイベントをソートして走査する（スイープライン）」の典型です。

計算量

• 時間計算量: \(O(N \log N)\)（開始・終了のソートが支配的）
• 空間計算量: \(O(N)\)（開始・終了配列）

実装のポイント

• 半開区間 \([S,E)\) なので、S == E のときは重ならない扱いにする必要があります。比較を starts[i] < ends[j] とし、等しい場合は終了を先に処理します。

• 入力が最大 \(2\times 10^5\) と大きいので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 走査ループは「開始をすべて処理するまで」で十分です（開始を \(N\) 回処理すれば、必要な最大同時開催数は確定するため）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    starts = [0] * n
    ends = [0] * n
    idx = 1
    for i in range(n):
        starts[i] = data[idx]
        ends[i] = data[idx + 1]
        idx += 2

    starts.sort()
    ends.sort()

    i = j = 0
    cur = ans = 0
    while i < n:
        if starts[i] < ends[j]:
            cur += 1
            if cur > ans:
                ans = cur
            i += 1
        else:
            cur -= 1
            j += 1

    print(ans)

if __name__ == "__main__":
    main()

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