Day 125-Q2 | 区間グラフの彩色（Interval Graph Coloring）

問題

半開区間 $[l_i, r_i)$ で表される $N$ 件の予定が与えられる。2つの予定が時間的に重なる場合、同じ部屋に割り当てることはできない。すべての予定を部屋に割り当てるのに必要な最小の部屋数 $K$ と、その割り当てを1つ出力せよ。

割り当ての構成方法は次のアルゴリズムに従う（出力を一意にするため）：

予定を $l_i$ の昇順（同じ $l_i$ なら入力順）にソートする。
使用中の部屋を、空く時刻 $r$ と部屋番号の組 $(r, \text{room})$ の最小ヒープで管理する。
各予定を処理し、ヒープ最小要素 $(r,\text{room})$ が $r \le l_i$ ならその部屋番号をそのまま再利用する。そうでなければ、まだ使われていない最小の部屋番号を新規に割り当てる。

入力形式

N
l_1 r_1
...
l_N r_N

制約

$1 \le N \le 200000$

$0 \le l_i < r_i \le 10^9$

入出力例

入力例1

出力例1

2
1 2 2

入力例2

出力例2

2
1 1 2 2

[1,5)と[5,10)は5=5で重ならない(半開区間)ので同じ部屋1を再利用できる。[2,6)と[6,9)も同様に部屋2を再利用

概念図

ヒント（段階的開示）

ヒント1（方向性）

必要な部屋数の下限は「同時刻に重なっている予定の最大数」である。この下限が実際に達成可能であることを、貪欲な部屋割り当てで示せないか考える。

ヒント2（アプローチ）

予定を開始時刻順に処理しながら、「今空いている部屋の集合」を管理する。新しい予定が来たら、空いている部屋があればそれを使い、なければ新しい部屋を用意する、という貪欲法が最適であることは、区間グラフが完全グラフ（Perfect Graph）であるという性質（最大クリークサイズ＝彩色数が常に一致する）から保証される。実装上は終了時刻が最小の使用中の部屋をヒープで管理し、それが今の開始時刻以下なら再利用する形にすると効率よく判定できる。

ヒント3（誘導）

問題文で指定されたアルゴリズムはシンプルで、「使用中の部屋」をヒープ1本だけで管理すれば十分である。ヒープの最小要素（最も早く空く部屋）だけ調べ、条件を満たせばその部屋番号をそのまま再利用し、満たさなければ新しい番号を払い出す。

import heapq

events.sort(key=lambda x: (x[0], x[2]))  # (l, r, 元のインデックス)
heap = []          # (終了時刻, 部屋番号)
next_room = 1
ans = [0] * n

for l, r, idx in events:
    if heap and heap[0][0] <= l:
        end, room = heapq.heappop(heap)
    else:
        room = next_room
        next_room += 1
    ans[idx] = room
    heapq.heappush(heap, (r, room))

模範解答 (Python)

import sys
import heapq


def solve():
    data = sys.stdin.read().split()
    n = int(data[0])
    idx = 1
    events = []
    for i in range(n):
        l = int(data[idx]); r = int(data[idx + 1]); idx += 2
        events.append((l, r, i))

    events.sort(key=lambda x: (x[0], x[2]))

    heap = []          # (終了時刻, 部屋番号)
    next_room = 1
    ans = [0] * n
    max_room = 0

    for l, r, orig_idx in events:
        if heap and heap[0][0] <= l:
            end, room = heapq.heappop(heap)
        else:
            room = next_room
            next_room += 1
            max_room = max(max_room, room)
        ans[orig_idx] = room
        heapq.heappush(heap, (r, room))

    print(max_room)
    print(' '.join(map(str, ans)))


solve()

Step-by-Step 解説

1必要部屋数の下限
任意の時刻 $t$ に対して、$t$ を含む予定の個数を $c(t)$ とすると、それらすべての予定は互いに重なっているため異なる部屋が必要になる。よって必要部屋数は $\max_t c(t)$ 以上である。これは区間グラフ上の最大クリークサイズに等しい。

2貪欲法が下限を達成すること（完全グラフ性）
区間グラフは完全グラフ（Perfect Graph）の一種であり、任意の誘導部分グラフにおいて彩色数とクリーク数が一致するという強い性質を持つ。この性質により、貪欲法は常に $\max_t c(t)$ 個の部屋で全予定を割り当てられることが保証される。

3なぜヒープの最小終了時刻だけ見ればよいのか
現在使用中の部屋の中で最も早く空く部屋の終了時刻が今の開始時刻 $l_i$ 以下でなければ、他のどの使用中の部屋も $l_i$ より後にしか空かない（ヒープの最小性）。したがってヒープの最小要素だけ調べるだけで、再利用可能な部屋の有無を正しく判定できる。

4半開区間の扱い
$[l_i, r_i)$ という半開区間の定義により、heap[0][0] <= l（等号を含む）で判定することが「時刻が一致するだけなら重ならない」という仕様と整合する。閉区間の問題であれば < を使う必要がある。

5計算量
ソートに $O(N \log N)$、各予定につきヒープ操作が定数回で $O(\log N)$ なので全体 $O(N \log N)$。

よくあるミス

ミス	原因	正しい書き方
`heap[0][0] < l` にしてしまう	境界条件の見落とし	半開区間 `[l, r)` では `<=` を使う
再利用時に部屋番号を振り直してしまう	「最小番号にすべき」という思い込み	問題の指定通り、ポップした部屋の番号をそのまま使う
彩色数の下限だけ求めて構成を省略する	存在性と構成可能性を混同	区間グラフでは完全グラフ性により貪欲構成で下限が必ず達成できることを説明・実装する
ソート時に $l$ が同じ予定の順序を無視する	タイブレークを決めていない	同じ $l$ なら入力順（元のインデックス）でソートする

次のステップ

発展: 各部屋の稼働率を最大化するなど、重み付き最適化に拡張すると「区間グラフ上の最小費用彩色」問題になり、フロー問題に帰着できる。
次回予告: Dinic法による最大流とLink-Cut Treeによる高速化の理論

自己評価

完全理解おおむね理解要復習

Day 125-Q2 — 区間グラフの彩色（Interval Graph Coloring）

問題