区間マージ
01 / 一文で言うと
始点でソートし、左から右へ走査する — 各区間は現在のマージ区間を右に伸ばすか、 それを確定して新しいマージを始めるかのどちらか。 パターンの全体はこの 1 つの比較に収まる。
問題すべての重なる区間をマージする入力[1,3] [2,6] [8,10] [15,18]
入力は 4 区間。下のバーは入力順に並んでいる。
ステップ
0 / 12
現在
—
結果
0
0 / 12
02 / パターンの骨格
# 始点でソートしてから走査intervals.sort(key=start)result ← []for [s, e] in intervals:if result が空 or result.last.end < s:result.push([s, e]) # 新たに確定else:result.last.end ← max(result.last.end, e) # 右に伸ばす# 重なり判定:result.last.end ≥ s(始点ソート後)
03 / このパターンを使うべき合図
「重なる区間をマージ」
最も典型的なシグナル。出力数は入力数を超えず、しばしば少なくなる。個数が変わらなければ、このパターンは単なる確認に縮む。
「会議 / 予約 / スケジュール」
カレンダー型の問題:会議室、フライト、社員の空き時間。区間は時間軸の意味を持つ。
「ソート済み区間への挿入」
バリエーション — 既にソート済みの区間列に 1 つ追加する。マージの論理は同じで、 新区間の入る位置までスキャンするだけ。
「最少削除で重ならなくする」
貪欲のバリエーション — 始点ではなく終点でソートし、いくつ削るかを数える。 ソートキーが違うだけで、スキャンの骨格は同じ。
04 / よくある落とし穴
ソートキーが間違っている。
マージでは
start でソート。「できるだけ多く重ならないように残す」貪欲では end でソート。これらは交換不能 — 終点でソートすると、 上のマージループは前の区間をまたぐ重なりを取りこぼす。「厳密な重なり」と「非厳密な重なり」。
[1, 3] と [3, 5] は重なる?問題文を 2 回読む。 端点接触を含めるなら条件は result.last.end ≥ s、含めないなら result.last.end > s。混同すると答えが反転する。そうすべきでない場面でその場改変する。
このパターンは自然にその場走査として書ける:取り出し、比較、直前にマージ、押し込み。 便利だが、後で呼び出し側が
intervals をまだ使う場合、そのデータを静かに壊している。 先にコピーすること。05 / LeetCode で練習
中級16
01Merge Intervals— LC 56→02Insert Interval— LC 57→03Meeting Rooms II— LC 253→04Non-overlapping Intervals— LC 435→05Minimum Number of Arrows to Burst Balloons— LC 452→06Add Bold Tag in String— LC 616→07Maximum Length of Pair Chain— LC 646→08My Calendar II— LC 731→09Partition Labels— LC 763→10Interval List Intersections— LC 986→11Video Stitching— LC 1024→12Car Pooling— LC 1094→13Remove Interval— LC 1272→14Remove Covered Intervals— LC 1288→15Divide Intervals Into Minimum Number of Groups— LC 2406→16Count Ways to Group Overlapping Ranges— LC 2580→
難しい9
01The Skyline Problem— LC 218→02Data Stream as Disjoint Intervals— LC 352→03Range Module— LC 715→04My Calendar III— LC 732→05Employee Free Time— LC 759→06Rectangle Area II— LC 850→07Maximum Profit in Job Scheduling— LC 1235→08Minimum Number of Taps to Open to Water a Garden— LC 1326→09Minimum Interval to Include Each Query— LC 1851→