区間マージ
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 / よくある落とし穴
i.
ソートキーが間違っている。
マージでは
start でソート。「できるだけ多く重ならないように残す」貪欲では end でソート。これらは交換不能 — 終点でソートすると、 上のマージループは前の区間をまたぐ重なりを取りこぼす。ii.
「厳密な重なり」と「非厳密な重なり」。
[1, 3] と [3, 5] は重なる?問題文を 2 回読む。 端点接触を含めるなら条件は result.last.end ≥ s、含めないなら result.last.end > s。混同すると答えが反転する。iii.
そうすべきでない場面でその場改変する。
このパターンは自然にその場走査として書ける:取り出し、比較、直前にマージ、押し込み。 便利だが、後で呼び出し側が
intervals をまだ使う場合、そのデータを静かに壊している。 先にコピーすること。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。