問題の概要と適用範囲
すべての要素が [start, end] かつ start <= end である閉区間の未ソートリスト intervals が与えられたとき、すべての重複をマージしてください。start でソートされ、互いに素（pairwise disjoint）であり、まったく同じ点をカバーする新しいリストを返します。この問題は閉区間を扱うため、[1, 4] と [4, 5] は点 4 を共有しており、[1, 5] にマージされなければなりません。この関数は入力を変更（mutate）してはなりません。
例：
Input: [[8, 10], [1, 3], [2, 6], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]入力は空の場合があり、重複する区間、負の端点、長さ 0 の区間、または他の区間に完全に含まれる区間を含むことがあります。基本問題では各要素に 2 つの有効な整数の端点が存在することが保証されているため、入力フォーマットのバリデーションはマージ関数の責務外です。これは一般的なソフトウェアエンジニアリングのコーディング問題です。その中核となるスキルは、任意の順序を局所的な判断が可能な順序に変換し、貪欲な判断が後続の接続を見落とさないことを証明することです。
面接官が評価するポイント
第一の評価ポイントは、候補者が区間のセマンティクスを定義しているかどうかです。閉区間、半開区間、そして単に隣接する範囲をマージするルールでは、それぞれ異なる条件が導かれます。契約を明示せずに start < current_end と書くと、端点を共有するケースで失敗する可能性があります。
第二の評価ポイントは、候補者がなぜソートが有効であるかを説明できるかどうかです。ソート後、次の start が現在の start より小さくなることはありません。もし次の start が現在マージ中の区間の end よりも既に大きい場合、それ以降のすべての start も確実に大きくなるため、現在の区間を安全に出力（確定）できます。優れた回答では、単に「ソートしてスキャンする」と言うだけでなく、この確定（finalization）の論拠を提示します。
第三の評価ポイントは、包含関係の処理です。[1, 10] が [2, 3] と出会った場合、マージ後の end は max(10, 3) でなければなりません。これを 3 で上書きしてしまうと、カバーされていた点が失われます。連鎖的な重複も、直前の元の入力区間だけでなく、拡張中のマージ済み区間と比較する必要があります。
面接官は、変更契約（mutation contract）、計算量、およびテスト・バリデーション戦略も確認します。通常、ソートが実行時間 O(n log n) を決定します。この実装では、入力を変更しないよう、ソートされたコピーと結果のために O(n) の空間を使用します。テストは標準的な例にとどまらず、入力が変更されていないこと、出力が整列され互いに素であること、そしてランダムな結果が低速な参照実装と一致することを検証（assert）すべきです。
回答前に確認すべき明確化のための質問
- これらは閉区間ですか、それとも半開区間ですか？また、端点の共有はマージ対象ですか？ ここでは閉区間であるため、条件は
next_start <= current_endです。プロダクト側で隣接を別個として扱う場合は、厳密な不等号比較を使用します。[a, b)の場合、連続しているが重複していない範囲をマージするかどうかは別の判断となります。 - 入力はすでに start でソートされていますか？ ソート済みの入力であれば線形スキャンのみで済むため、時間は
O(n)に短縮されます。未ソートの場合はソート、あるいは有界な端点ドメインに特化した手法が必要です。 - 入力を変更（mutate）してもよいですか？ 可能な場合は、インプレースでソートし、書き込みポインタで圧縮します。不可能な場合は、データをコピーするか、新しいリストを返すソート操作を使用します。
- 端点は小さな有界範囲の整数ですか？ 任意の比較可能値に対しては、比較ソートが直接的な選択肢です。小さな整数領域であればバケットソートや差分配列（difference array）を利用できる可能性がありますが、そのコストは
nだけでなく座標範囲にも依存します。 - これは 1 回限りのオフラインマージですか、それとも継続的なストリームですか？ start 順に並んだストリームは、オンラインでマージして出力できます。任意の順序のストリームは、将来の区間がより早い start を持ち、既存のコンポーネントを橋渡しする可能性があるため、早期に安全に確定することはできません。
- 出力には境界のみが必要ですか、それとも区間のメタデータを保持する必要がありますか？ 境界のマージだけでは、ラベル、権限、価格などをどのように統合するかは定義されません。メタデータには明示的な集約ルールが必要です。
30秒の回答フレームワーク
「まず、これらが閉区間であること、共有された端点は重複とみなすこと、そして入力を変更してはならないことを確認します。start と end でコピーしてソートし、1 つの現在マージ中の区間を保持します。次の start が現在の end 以前であれば、end を 2 つの end の最大値に拡張します。そうでなければ、後続の区間が現在の区間に届くことはないため、現在の区間を追加して新しい範囲を開始します。スキャン終了後に最後の範囲を追加します。ソートのコストは O(n log n)、スキャンのコストは O(n) であり、ソートされたコピーと出力は O(n) の空間を使用します。正当性の不変条件は、出力された区間は確定済みであり、現在の区間は処理済みの中でまだ出力されていない最後の連結成分そのものであるということです。」
ステップごとの詳細解説
直接的なアプローチとしては、重複するペアを繰り返し見つけてその和集合に置き換え、変化がなくなるまで再起動する方法があります。これは二重ループで簡単に表現できますが、新しくマージされた区間が既に検査されたものと重複する可能性があるため、多数のパスが必要となり O(n²) 以上に達することがあります。その手法は小規模な入力に対するテストオラクルとしては有用ですが、第一の解決策としては不適切です。
ソートにより、全体最適の問題が左から右へのスキャンに変換されます。(start, end) の昇順でソートします。処理済み区間のうち、まだ出力されていない最後のマージ済みコンポーネント current = [current_start, current_end] を保持します。各次の [start, end] に対して：
start <= current_endの場合、2 つの閉区間は重複しているため、current_endをmax(current_end, end)に更新します。start > current_endの場合、隙間（ギャップ）が存在します。これ以降のすべての start は少なくともstartであるため、将来の区間がcurrentに届くことはありません。これを出力し、新しい現在の区間を開始します。
このスキャンは 3 つの不変条件（invariants）を維持します：
- 出力された区間はソートされており、互いに素であり、二度と変更されない。
- 出力された区間と
currentの和集合は、処理されたすべての入力区間の和集合と等しい。 currentは、処理された区間の中で最後の極大なマージ済みコンポーネントであり、次の区間と重複し得る唯一のコンポーネントである。
これら 3 つは、最初のソート済み区間で初期化した後も成立します。重複は最後のコンポーネントの右端点を拡張するだけであり、その和集合を保持します。ギャップがある場合、ソートによって将来のすべての start が current_end より先にあることが保証されるため、安全に出力できます。数学的帰納法により、これらの不変条件はスキャン全体を通じて維持されます。最後に current をもう一度出力することで、どのペアもこれ以上マージできない同等な和集合が生成されます。
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
ordered = sorted((start, end) for start, end in intervals)
merged: list[list[int]] = []
current_start, current_end = ordered[0]
for start, end in ordered[1:]:
if start <= current_end:
current_end = max(current_end, end)
else:
merged.append([current_start, current_end])
current_start, current_end = start, end
merged.append([current_start, current_end])
return mergedsorted() は新しいソート済みリストを構築し、タプルを展開しても元の内部リストは書き換えられないため、この関数は非破壊契約を遵守します。比較ソートのコストは O(n log n)、スキャンのコストは O(n) であり、全体で O(n log n) となります。ソートされたコピーと、最大ですべての n 個の区間を含む可能性のある出力はどちらも線形であるため、出力を含む空間計算量は O(n) です。入力が既にソートされている場合、ソートを省略すると O(n) の時間になります。変更が許可されている場合は、インプレースソートと書き込みポインタにより入力を再利用できますが、ソートの実装自体にスタックやバッファ空間が必要となる場合があります。
バリデーションでは、空の入力、1 つの区間、すべてが互いに素な区間、共有された端点、完全な包含、重複、負の端点、連鎖的な重複を網羅すべきです。例えば、[[1, 2], [2, 3], [3, 4]] は [[1, 4]] にならなければなりません。これは、隣接する生の入力区間のみを比較しているコードを検出します。ディープコピーを保持し、関数呼び出しによってそれが変更されないことをアサートしてください。その後、小さなランダム入力を生成し、重複ペアを繰り返しマージする低速なオラクルと比較します。上記の実装は、固定シードによる 10,000 件のランダムケースで差分テスト（differential-tested）が行われています。
比較モデルにおける任意の値に対しては、ソート＆スキャンが明確な一般的解答です。n が非常に小さい場合、ペアの繰り返しマージの方がコードが短くなり、計算量の上限の遅さも問題にならないことがあります。既にソートされた入力にはスキャンのみが必要です。小さな有界整数ドメインであれば、座標範囲に依存するバケットや差分配列の手法が正当化される場合があります。面接では、制約によって正当化された場合にのみ、このような特殊なケースを提示してください。
高品質な回答例
「まず境界条件を明確にします。入力には未ソートの閉区間が含まれ、端点の共有は重複とみなし、新しいデータを返す必要があります。つまり、[1, 4] と [4, 5] は以下（less-than-or-equal）のテストを使用します。
総当たり（brute-force）版では、ペアを見つけて再起動を繰り返すことができますが、新しくマージされた区間がそれ以前に見たものと重複する可能性があるため、多数のパスが必要になる場合があります。私は start でソートし、まだ確定していない 1 つの区間のみを保持します。次の start がその end の内側にある場合、より大きい end で拡張します。そうでなければ、結果に書き出して新しいコンポーネントを開始します。
重要なのは、直前の生の区間ではなく、蓄積されたコンポーネントと比較することです。ソートにより、次の start が現在の end を超えると、それ以降のすべての start も超えることが保証されるため、現在の結果は恒久的に確定します。したがって、出力されたプレフィックスは整列され互いに素な状態を保ち、現在の区間は処理済み入力の最後のマージ済みコンポーネントを正確にカバーします。
呼び出し元のリストを変更しないよう sorted() を使用し、空の入力に対しては早期リターンします。時間はソートと線形スキャンで O(n log n)、ソートされたコピーと出力は O(n) の空間を使用します。接している区間、入れ子、重複、負の値、連鎖した区間をテストし、入力が変更されていないことをアサートしつつ、低速なペア単位のマージに対して差分テストを行います。」
よくある間違い
- 端点のセマンティクスを定義せずに
<または<=を選択する → 共有端点の結果は契約に依存する → 条件を選択する前に、閉区間か半開区間か、および連続する範囲をマージするかどうかを明示する。 - 元の順序のままスキャンする → 重複する区間が遠く離れている可能性があり、将来の区間が出力済みの結果を再接続する場合がある → ソート済み入力が保証されていない限り、start でソートする。
- 隣接する生の入力区間のみを比較する →
[1, 10],[2, 3],[9, 12]の 3 番目の要素は、拡張された[1, 10]と照合されなければならない → 常に直前のマージ済み結果と比較する。 - 重複時に
current_end = endを代入する → 包含された区間によってカバー範囲が縮小してしまう →max(current_end, end)を使用する。 - 最後の追加を忘れる → ギャップでのみ出力するループは最後のコンポーネントを失う → ループの後に一度だけ
currentを追加する。 - 空の入力に対して最初の要素を読み取る → 初期化時にインデックスエラーが発生する → ソートおよび初期化の前に空のリストを返す。
- 非破壊を約束しながらインプレースでソートする → 呼び出し元から見て入力の順序が変わり、再利用された内部リストが変更され続ける可能性がある →
sorted()と新しい結果オブジェクトを使用するか、変更を契約の一部とする。 - 期待される配列のみをテストする → 連鎖的な重複、変更、境界エラーが見逃される可能性がある → プロパティチェックとランダム化された差分オラクルを追加する。
O(n log n)が常に不可避であると主張する → ソート済みの入力や小さな有界整数ドメインでは比較ソートを回避できる → 下限の主張は、未ソートの任意の比較可能な端点に限定する。
発展質問と対策
発展質問 1: 共有された端点を重複とみなさない場合、何が変わりますか？
条件を start <= current_end から start < current_end に変更します。まずドメインの定義を確認してください。端点を共有する閉区間は数学的には交差するため、それらを別々に保つプロダクトは、実際には長さが正の重複のみをマージすることを求めています。半開区間 [a, b) の場合、[1, 4) と [4, 5) は重複しません。連続する範囲をマージするかどうかは、別の独立したルールになります。
発展質問 2: 入力がソート済みで変更が許可されている場合、追加の空間をどのように削減できますか？
ソートを省略し、書き込みポインタを用いて入力のプレフィックスに圧縮します。読み取りポインタが新しい区間を走査します。重複時は書き込み位置の end を更新し、ギャップ時は書き込みポインタを進めて新しい区間をコピーします。プレフィックスの長さ、またはそのプレフィックスのビューを返します。スキャンには元の入力を破壊する代償として、O(n) の時間と、返される表現を除いて O(1) の補助空間がかかります。
発展質問 3: 区間が start 順に継続的に到着します。ストリームとして出力できますか？
はい。current のみを保持します。到着した start がその end を超えたら、current を出力して次のコンポーネントを開始します。ストリームが閉じたときに最後のコンポーネントを出力します。作業メモリは出力を除いて O(1) です。到着順序が任意である場合、将来の区間が 2 つのコンポーネントを橋渡しする可能性があるため、早期の出力は安全ではありません。代わりにバッファリング、外部ソート、または動的な区間構造を維持します。
発展質問 4: 1 億個の区間がメモリに収まらない場合はどうしますか？
start による外部ソート（external sort）を使用します。メモリサイズのバッチをソートして整列されたラン（run）にし、k 方向マージ（k-way merge）を実行します。マージストリームはすでに start 順になっているため、最初に完全にグローバルソートされたファイルを実体化するのではなく、マージを行いながら同じ 1 区間の状態マシンを実行します。比較の計算量は O(n log n) のオーダーのままですが、ディスク I/O と一時ストレージが重要な追加コストとなります。
発展質問 5: 価格や権限ラベルを持つ区間を直接マージできますか？
このアルゴリズムで結合できるのは、幾何学的な境界のみです。重複するセグメントが異なるラベルを持っている場合、それらを 1 つのラベルに統合すると情報が失われます。出力にラベルのセットを持たせるか、最優先のラベルを持たせるか、あるいはメタデータが一定である最小のサブセグメントを持たせるかを定義します。最後の選択肢は通常、単純な区間の和集合ではなく、端点イベントに対する走査（スウィープライン法）が必要になります。