概要

与えられた会議のスケジュールに対して、時間帯が重ならないように会議室を割り当てたとき、必要な会議室の最小数を求める問題です。

考察

この問題は「区間スケジューリング」の応用形です。素朴な方法として、すべての会議を順番に見て、すでに使われている会議室のどれかに入れられるかを調べる方法があります。しかし、会議の数 \(N\) が最大で \(2 \times 10^5\) あるため、毎回すべての会議室を確認していたのでは計算時間がかかりすぎてしまいます（TLE）。

重要な着眼点は、「最も早く終わる会議室に次の会議を入れるのが最適」という点です。これにより、無駄に新しい会議室を使わずに済みます。この方針を効率よく実現するために、終了時刻を管理する優先度付きキュー（ヒープ） を使うのが有効です。

また、会議を開始時刻順に処理することで、常に「今後の会議に影響を与える可能性がある会議」から順に処理できます。

例えば、次のような入力を考えましょう：

3
1 3
2 4
3 5

開始時刻でソートすると順番に処理されます： - 会議 [1, 3)：会議室を新たに使う → ヒープに 3 を追加 - 会議 [2, 4)：まだ空きがないので新たな会議室を使う → ヒープに 4 を追加 - 会議 [3, 5)：最初の会議が終わったので、その部屋を再利用 → ヒープの 3 を取り出し、5 を追加

最終的にヒープのサイズが答え（使用した会議室数）になります。

アルゴリズム

1. すべての会議を開始時刻 \(S_i\) の順にソートします。
2. 優先度付きキュー（min-heap）を用意し、各会議室の「最も遅い終了時刻」を管理します。
3. 各会議について以下のように処理します：
   • ヒープの最小値（最も早く終わる会議室の終了時刻）が現在の会議の開始時刻より前であれば、その会議室を再利用（ヒープから取り出して新しい終了時刻を追加）。
   • そうでなければ、新しい会議室を使う（ヒープに終了時刻を追加）。
4. 最終的なヒープのサイズが使用する会議室の最小数です。

計算量

• 時間計算量: \(O(N \log N)\)
  （ソートに \(O(N \log N)\)、各要素のヒープ操作に \(O(\log N)\)）
• 空間計算量: \(O(N)\)
  （ヒープに最大 \(N\) 個の要素を持つ）

実装のポイント

• 会議を開始時刻でソートすることを忘れない。

• ヒープには終了時刻のみを入れる。

• heap[0] で最も早い終了時刻を取得できる（Pythonのheapqでは最小ヒープ）。

• 同じ開始・終了時刻の会議が複数ある場合も正しく処理される。

  ソースコード

import heapq

N = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(N)]

# 開始時刻でソート
meetings.sort()

# 終了時刻を管理する優先度付きキュー
heap = []

for s, e in meetings:
    # 一番早く終わる部屋が使えるかどうかチェック
    if heap and heap[0] <= s:
        heapq.heappop(heap)
    # 現在の会議の終了時刻を追加
    heapq.heappush(heap, e)

print(len(heap))

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