スイープライン
01 / 一文での本質
区間を始点 +1、終点 −1 の 2 つのイベントに分解し、 位置でソートして走査する — イベントごとに現在のアクティブ数が 1 だけ動く。 答えはこの階段関数の何らかの性質。
問題同時最大区間数入力[0,30] [5,10] [15,20]
入力は 3 区間。それぞれ始点で +1、終点で −1 のイベントを 1 つずつ提供する。
ステップ
0 / 9
アクティブ
0
ピーク
—
0 / 9
02 / パターンの骨格
# 区間 → 端点イベントevents ← []for [s, e] in intervals:events.push((s, +1))events.push((e, −1))events.sort() # 同位置の順序は問題次第active ← 0; best ← 0for (x, d) in events:active += dbest ← max(best, active)# `best` が最大同時数 — 最も典型的な答え
03 / このパターンを使うべき合図
「同時に最大 / 最大同時数」
教科書的なトリガー。重なる会議、同時に空にいる飛行機、高速の車、勤務中の社員 — アクティブ数のピークが知りたいときはいつでも。各区間が +1 と −1 を 1 つずつ提供し、残りは数えるだけ。
「予約 / 乗降 / 容量」
予約リストを装った容量チェック。ソートして走査するだけで超過の有無が分かる。 最初の違反で早期 return も簡単。
「区間 — 各点で何が成り立つか」
答えがイベントの間で変わらないとき。階段関数は端点でしか変わらないので、 イベントを走査するだけで時間軸上の異なる瞬間を全部カバーできる。
「スカイライン / 被覆 / 区間和」
スイープライン + 補助データ構造(ヒープ、平衡 BST、multiset)。 各イベントで値を挿入/削除し、その x での答えは構造体のトップから読み取る。
04 / よくある落とし穴
i.
同位置のイベントの並び順。
同じ x に
+1 と −1 が来るとき、順序で答えが変わる。会議の重なり(端点接触を重なりに数える)なら +1 を先に。車の乗客数(同じ駅では先に降りる)なら −1 を先に。 骨格は同じ、タイブレークが逆。ii.
「区間マージ」と混同する。
区間マージは重なる範囲を 1 区間に潰してグループ数を数える; スイープラインは時間軸全体の走行深さを追う。両者とも始点でソートするが、 −1 イベントを気にするのはスイープラインだけ — それがないと深さが下がる瞬間が見えない。
iii.
イベント間にもアクティブ数があることを忘れる。
アクティブ数は
(prev_x, x] の区間で一定 — イベント間は変化しない。 「アクティブ数がちょうど k である時間の長さ」を問われたら、 イベント数ではなく active == k の区間長を足す。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。