概要

\(N\) 件の時間区間が与えられたとき、時間が重ならないように会議室に割り当てる際に必要な会議室数の最小値を求める、いわゆる「区間スケジューリング（Interval Partitioning）」問題です。

考察

重要な気づき：同時に行われている会議の最大数が答え

ある瞬間に \(k\) 件の会議が同時に進行しているなら、その瞬間だけで最低 \(k\) 部屋が必要です。逆に、貪欲法を用いれば「同時進行の最大数」ちょうどの部屋数で全会議を割り当てられることが知られています。

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

すべての会議のペア \((i, j)\) について重なりを確認すると \(O(N^2)\) かかり、\(N \leq 2 \times 10^5\) では TLE になります。

解決策：貪欲法 + 最小ヒープ

会議を開始時刻の昇順にソートし、順に処理します。各会議を割り当てるとき、「すでに使っている会議室のうち、最も早く空く部屋」が新しい会議の開始時刻以前に終了していれば、その部屋を再利用できます。これを効率的に判定するために最小ヒープ（優先度付きキュー）を使います。

具体例

会議が \([1,4), [2,5), [4,7)\) の 3 件あるとします。

1. 会議 \([1,4)\)：ヒープは空なので新しい部屋を使う → ヒープ: \(\{4\}\)
2. 会議 \([2,5)\)：ヒープの最小値 \(4 > 2\) なので再利用不可、新しい部屋 → ヒープ: \(\{4, 5\}\)
3. 会議 \([4,7)\)：ヒープの最小値 \(4 \leq 4\) なので再利用可能、\(4\) を取り出して \(7\) を追加 → ヒープ: \(\{5, 7\}\)

最終的にヒープのサイズは \(2\) → 答えは 2 です。

アルゴリズム

1. \(N\) 件の会議を開始時刻 \(S_i\) の昇順（同じなら終了時刻 \(E_i\) の昇順）にソートする。
2. 各会議室の終了時刻を管理する最小ヒープを用意する。
3. ソート順に会議 \((S_i, E_i)\) を処理する：
   • ヒープが空でなく、ヒープの最小値（最も早い終了時刻）が \(S_i\) 以下なら、その部屋を再利用する（ヒープから最小値を取り出す）。
   • ヒープに \(E_i\) を追加する（再利用の場合は部屋の終了時刻を更新、新規の場合は部屋を追加）。
4. 最終的なヒープのサイズが、必要な会議室の最小数。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、ヒープ操作が各会議あたり \(O(\log N)\)）
• 空間計算量: \(O(N)\)（ヒープに最大 \(N\) 個の要素が入る）

実装のポイント

• 半開区間 \([S_i, E_i)\) なので、ある会議の終了時刻と別の会議の開始時刻が一致する場合（\(E_j = S_i\)）は重ならない。コード中の条件 heap[0] <= s がこれを正しく処理している（< ではなく <=）。

• Python の heapq モジュールは最小ヒープを提供するので、「最も早く終わる部屋」を \(O(\log N)\) で取得できる。

• ソート時にタプル \((S_i, E_i)\) を使うと、Python は第1要素 → 第2要素の順で比較するため、自然に開始時刻順・同率なら終了時刻順になる。

  ソースコード

import heapq

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    meetings = []
    for _ in range(N):
        s, e = map(int, input().split())
        meetings.append((s, e))
    
    # Sort by start time, then by end time
    meetings.sort()
    
    # Min-heap of end times of currently used rooms
    heap = []
    
    for s, e in meetings:
        if heap and heap[0] <= s:
            heapq.heappop(heap)
        heapq.heappush(heap, e)
    
    print(len(heap))

main()

---

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