区間スケジューリング

一つの資源で重ならない区間を最大数選びます。終了時刻で並べ、最初の互換な区間を受け入れます。重みなしで個数最大化なら最適で、全時間は O(n log n) です。

早く始まる会議が有利とは限らず、一日中部屋を占めることもあります。早く終われば後の要求に場所を返せます。

区間スケジューリングの仕組み

区間は半開の [start, end)。5 に終了する会議と 5 に始まる会議は接触しても重なりません。

last_end は最後に受け入れた終了時刻です。end 順に走査します。

1. start >= last_end なら受け入れ、last_end = end。
2. start < last_end なら拒否し、境界を変えない。

拒否した要求は日程に入らず、互換性の境界も動かせません。

交換論証

任意の最適日程 O の次の区間と貪欲選択を比べます。貪欲側は互換な候補の中で最も早く終わるため、O の次を置き換えても後続はすべて入り、個数も不変です。残りにも繰り返すと、最適日程を一つも失わず貪欲日程へ変えられます。

証明欄は具体的な O を示しますが、論証はそれだけに限定されません。任意の最適解に適用できるので、貪欲と最適の数は同じです。四つ見つけただけでなく、五つ選ぶ日程がないと分かります。

選択をステップで追う

入力順は次です。

A=[0,3)、B=[5,7)、C=[1,2)、D=[6,9)、E=[3,5)、F=[4,6)、G=[7,9)、H=[2,5)。

終了、開始、安定した入力順で並べ、C, A, H, E, F, B, D, G になります。

1. C [1,2) を受け入れ、last_end = 2。
2. A [0,3) は 0 < 2 で拒否。境界 2 のまま。
3. H [2,5) は開始が 2 と等しく受理、境界 5。
4. E [3,5) は 5 より早く始まるので拒否。
5. F [4,6) も拒否。
6. B [5,7) は境界に接し、受理して 7。
7. D [6,9) は 7 より早く、拒否。
8. G [7,9) は接触するので受理、境界 9。

選択は C, H, B, G。四つ残し、四つ除きます。

証明欄は別の最適 A, E, B, G から始めます。A を C へ換えると終了が 3 から 2 に早まり、後続は入ります。E を H へ換えても終了は 5 のまま。B と G は一致済みです。個数四を保ち、貪欲結果になります。

この入力は最早開始順も A, E, B, G となりますが、偶然の同点は正しさの証明ではありません。Long blocker では最早開始が一つ、最早終了が七つです。

最少削除版は minimum removals = n - maximum compatible count で、LeetCode 435 と同じ目的です。

画面の縦線は last_end。受理した区間は chosen 欄へ移って線を進め、拒否したものは重なりを示すだけで線を動かしません。

時間・空間計算量

終了順なら走査だけで O(n)。表示コードは ordered に入力をコピーし、chosen を保存するので空間 O(n)。それ以外は last_end 一つで O(1) です。

境界ケース

• 空：空日程。編集画面は一つ以上を要求するが、生成器は空も処理する。
• 一区間：即受理。
• 全区間が互いに衝突：一つだけ選べ、終了の早い互換候補を取る。
• 端点接触：[0,2) と [2,4) は互換で >= が必要。
• 同じ終了：現在互換な候補の同点は個数最適性を変えない。ここは開始時刻と安定入力順で決める。
• 重み付き：価値総和の最大化では、個数を保つ交換だけでは足りず、重み付き区間 DP などが必要。

よくある間違い

• 最早開始で並べる。 長い要求が後続を塞ぎ、Long blocker では一対七です。
• 最短期間で並べる。 真ん中の短区間が前後を両方塞ぐことがあり、同じ交換証明は使えません。
• start > last_end。 合法な連続区間を拒否します。
• 拒否でも境界を変える。 境界は最後の受理区間のものです。
• 閉区間と半開区間を混ぜる。 両端を占有する用途なら接触も衝突し得るため、比較を規約に合わせます。
• 重みにも同じ証明を使う。 保つのは個数で、任意の価値ではありません。