スイープライン
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 / よくある落とし穴
同位置のイベントの並び順。
同じ x に
+1 と −1 が来るとき、順序で答えが変わる。会議の重なり(端点接触を重なりに数える)なら +1 を先に。車の乗客数(同じ駅では先に降りる)なら −1 を先に。 骨格は同じ、タイブレークが逆。「区間マージ」と混同する。
区間マージは重なる範囲を 1 区間に潰してグループ数を数える; スイープラインは時間軸全体の走行深さを追う。両者とも始点でソートするが、 −1 イベントを気にするのはスイープラインだけ — それがないと深さが下がる瞬間が見えない。
イベント間にもアクティブ数があることを忘れる。
アクティブ数は
(prev_x, x] の区間で一定 — イベント間は変化しない。 「アクティブ数がちょうど k である時間の長さ」を問われたら、 イベント数ではなく active == k の区間長を足す。05 / LeetCode で練習
簡単4
中級9
01Meeting Rooms II— LC 253→02Range Addition— LC 370→03Non-overlapping Intervals— LC 435→04Minimum Number of Arrows to Burst Balloons— LC 452→05My Calendar II— LC 731→06Car Pooling— LC 1094→07Corporate Flight Bookings— LC 1109→08Shifting Letters II— LC 2381→09Divide Intervals Into Minimum Number of Groups— LC 2406→
難しい15
01The Skyline Problem— LC 218→02Contains Duplicate III— LC 220→03Count of Smaller Numbers After Self— LC 315→04Count of Range Sum— LC 327→05Perfect Rectangle— LC 391→06Reverse Pairs— LC 493→07My Calendar III— LC 732→08Employee Free Time— LC 759→09Rectangle Area II— LC 850→10Maximum Profit in Job Scheduling— LC 1235→11Minimum Number of Taps to Open to Water a Garden— LC 1326→12Minimum Interval to Include Each Query— LC 1851→13Minimum Cost to Reach Destination in Time— LC 1928→14Meeting Rooms III— LC 2402→15Minimum Time to Complete All Tasks— LC 2589→