問題
$N$ 件の会議が与えられる。$i$番目の会議は区間 $[l_i,r_i)$（$l_i$に開始し$r_i$に終了。終了時刻と別会議の開始時刻が同じ場合は重複しないとみなす）で行われる。すべての会議を、同時刻に同じ部屋で2件以上重ならないように部屋へ割り当てるとき、必要な最小の部屋数を求めよ。
これはDay153の「重み付き区間スケジューリング」（DPで選ぶ部分集合の重みを最大化）とは異なり、全ての会議を必ず開催する前提で、同時に必要なリソース（部屋）の最大数を求める問題である。
入力形式
N
l_1 r_1
...
l_N r_N制約
$1\le N\le 2\times 10^5$
$0\le l_i<r_i\le 10^9$
入出力例
入力例1
3
0 30
5 10
15 20出力例1
2入力例2
4
1 5
2 6
4 7
8 9出力例2
3概念図：会議のタイムライン（入力例1）
ヒント（段階的開示）
ヒント1（方向性）
「どの部屋にどの会議を入れるか」を具体的に決めようとすると組み合わせ爆発するが、聞かれているのは必要な部屋数（最小値）だけである。ある時刻において同時に進行中の会議の数の最大値こそが必要な部屋数の下限であり、かつ実際に達成可能な上限でもある——という視点に切り替える。
ヒント2（アプローチ）
会議を開始時刻でソートし、使用中の部屋の終了時刻を最小ヒープで管理する（$O(N\log N)$）。新しい会議が来たとき、ヒープの最小終了時刻がその会議の開始時刻以下ならその部屋を再利用でき、そうでなければ新しい部屋が必要になる。
ヒント3（誘導）
import heapq
def min_rooms(intervals):
intervals.sort()
heap = []
ans = 0
for l, r in intervals:
while heap and heap[0] <= l:
heapq.heappop(heap)
heapq.heappush(heap, r)
ans = max(ans, len(heap))
return ans模範解答 (Python)
import sys
import heapq
def solve():
data = sys.stdin.read().split()
idx = 0
N = int(data[idx]); idx += 1
intervals = []
for _ in range(N):
l = int(data[idx]); r = int(data[idx + 1]); idx += 2
intervals.append((l, r))
intervals.sort()
heap = [] # 現在使用中の部屋が空くタイミング（終了時刻）の最小ヒープ
ans = 0
for l, r in intervals:
# 開始時刻 l 以前に終わっている部屋はすべて解放する
while heap and heap[0] <= l:
heapq.heappop(heap)
heapq.heappush(heap, r)
ans = max(ans, len(heap))
print(ans)
solve()Step-by-Step 解説
1「同時進行数の最大値」に言い換える
各会議を「開始時刻に+1、終了時刻に-1」のイベントとして時間軸上に並べ、走査しながら合計を追跡すると、その合計の最大値が必要な部屋数になる（区間の重なりの最大深さ）。
各会議を「開始時刻に+1、終了時刻に-1」のイベントとして時間軸上に並べ、走査しながら合計を追跡すると、その合計の最大値が必要な部屋数になる（区間の重なりの最大深さ）。
2実測トレース（入力例1）
ソート済み: (0,30),(5,10),(15,20)。l=0,r=30: heap=[30]、使用中=1。l=5,r=10: 30>5で解放なし、heap=[10,30]、使用中=2。l=15,r=20: 10<=15で10を解放、heap=[20,30]、使用中=2。最大使用数=2。実際にPythonで実行し2を確認済み。
ソート済み: (0,30),(5,10),(15,20)。l=0,r=30: heap=[30]、使用中=1。l=5,r=10: 30>5で解放なし、heap=[10,30]、使用中=2。l=15,r=20: 10<=15で10を解放、heap=[20,30]、使用中=2。最大使用数=2。実際にPythonで実行し2を確認済み。
3なぜこの貪欲が正しいか
ある会議が始まる時点で最も早く空く部屋（ヒープの先頭）がその会議の開始時刻以前に終わっているなら必ず再利用できる（交換論法）。最も早く空く部屋すら間に合わないなら他のどの部屋も間に合わないので新しい部屋が必要になる。
ある会議が始まる時点で最も早く空く部屋（ヒープの先頭）がその会議の開始時刻以前に終わっているなら必ず再利用できる（交換論法）。最も早く空く部屋すら間に合わないなら他のどの部屋も間に合わないので新しい部屋が必要になる。
4境界ケースの確認（入力例2）
ソート済み: (1,5),(2,6),(4,7),(8,9)。時刻4付近で(1,5),(2,6),(4,7)の3件が同時進行するため3部屋必要——実際にPythonで3を確認済み。
ソート済み: (1,5),(2,6),(4,7),(8,9)。時刻4付近で(1,5),(2,6),(4,7)の3件が同時進行するため3部屋必要——実際にPythonで3を確認済み。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 終了時刻と開始時刻の一致を「重なっている」と誤判定 | heap[0]<lではなくheap[0]<=lにすべきところを取り違える | 半開区間の定義に合わせ<=で解放する |
| ソートを終了時刻で行ってしまう | Day153のDP型スケジューリングの作法と混同 | 今回は開始時刻でソートしヒープで終了時刻を管理する |
| ヒープに会議番号なども積んでオーバーヘッドを増やす | 必要な情報を絞り込めていない | ヒープには終了時刻のみを積めば十分 |
| 境界値(N=0や全会議が重ならないケース)のテスト漏れ | 境界値のテスト設計漏れ | 会議が1件以上あればans>=1になることを確認する |
次のステップ
- 発展: 部屋ごとに「最初にその部屋を使った会議番号」を記録し、実際の部屋割り当てまで復元する。
- 次回予告: 逆BWT（Inverse Burrows-Wheeler Transform・LFマッピング）