問題と適用可能なコンテキスト
配列 A と B が与えられます。各要素は閉区間 [start, end] です。両方の配列は広義単調増加の start でソートされており、同一配列内の区間同士は重複しません。両方のリストでカバーされるすべての区間を、同様に開始順で返してください。
A = [[1,5],[10,14]] と B = [[2,3],[4,12]] の場合、積集合は [[2,3],[4,5],[10,12]] となります。端点が一致する場合も含まれるため、[1,2] と [2,4] は [2,2] で交差します。
面接官が見ているポイント
面接官は、すべてのペアを比較するのではなく、2つのソート済みシーケンスを単調な2ポインタ走査に変換できるかを見ています。優れた回答では、閉区間のセマンティクスを定義し、max(start) と min(end) を計算し、終了位置が早い方の区間のみを破棄できる理由を証明します。
コーディング前の確認事項
- 区間は閉区間ですか、それとも半開区間ですか？これにより、等しい端点が出力を生成するかどうかが変わります。
- 両方のリストはソートされており、内部で重複はありませんか？そうでない場合は、まず各リストをソートするかマージします。
- 入力は空、点区間を含む、または
start > endを含む可能性がありますか？これによりバリデーションが決まります。 - 長さ0の交差区間は保持すべきですか？閉区間であるため、この問題では保持します。
30秒回答フレームワーク
「ポインタ i と j を保持します。現在の交差区間は大きい方の開始値から始まり、小さい方の終了値で終わります。左端点が右端点以下である場合に出力します。その後、終了値が小さい方の区間を進めます。後続の開始値は、すでに終了した区間と重複することができないためです。終了値が等しい場合は、両方を進めます。各ポインタはそれぞれのリストを一度だけ走査するため、出力領域を除いて作業領域 O(1)、計算量 O(m+n) の走査となります。」
ステップごとの詳細解説
ステップ 1: 区間のセマンティクスを固定する
各区間を [start,end] として扱います。left = max(A[i].start, B[j].start) および right = min(A[i].end, B[j].end) とします。左端点が右端点以下である場合に交差が存在し、端点が等しい場合は有効な点を形成します。
ステップ 2: ポインタの移動を導出する
A[i].end が B[j].end 未満の場合、A[i] が先に終了します。B 内のそれ以降のすべての区間は B[j] 以降に始まるため、A[i] は B[j+1] またはそれ以降のものと交差することはできません。i を進めます。B[j] が先に終了する場合も対称です。
ステップ 3: 等しい終了位置を処理する
終了位置が等しい場合、現在のどちらの区間も後続の区間と重なり得る残りの時間がありません。両方のポインタを進めます。片方のみを進めると、処理済みの区間を再確認することになり、無駄な比較が生じたり証明が不明瞭になったりする可能性があります。
ステップ 4: 実行可能なスケルトンを記述する
function intersect(A: number[][], B: number[][]): number[][] {
const out: number[][] = [];
let i = 0;
let j = 0;
while (i < A.length && j < B.length) {
const left = Math.max(A[i][0], B[j][0]);
const right = Math.min(A[i][1], B[j][1]);
if (left <= right) out.push([left, right]);
if (A[i][1] < B[j][1]) i++;
else if (B[j][1] < A[i][1]) j++;
else { i++; j++; }
}
return out;
}ステップ 5: 正当性のための不変条件を述べる
各ループの開始時において、i と j は、交差できないことがまだ証明されていない最も早いペアを識別します。[left,right] はそのペアの唯一の可能な交差区間であるため、それを出力すればそのペアについては完了です。終了が早い方の区間を破棄した後、スキップされたすべてのペアは、すでに終了した区間よりも後の開始値を持つため、交差区間が見落とされることはありません。
ステップ 6: 計算量と入力検証を分析する
ポインタは進むだけであり、最大でも m+n 回しか移動しないため、時間は O(m+n) です。作業領域は出力を除いて O(1)、出力される k 個の区間を含めると O(k) です。ソートおよび有効な端点が保証されていない場合は、まずバリデーションまたは正規化を行います。線形の証明は任意の入力には適用されません。
質の高い模範解答
まず閉区間であること、開始位置がソートされていること、各リスト内で重複がないことを確認します。A[i] と B[j] について、交差区間は大きい方の開始値と小さい方の終了値を使用します。閉端点の場合、一方の端点が他方の端点以下であれば点が出力されます。次に、区間が先に終了する方のポインタを進めます。後続の開始値はすでに終了した区間と重複できないためです。終了値が等しい場合は両方を進めます。各区間は一度だけ処理されるため、時間は O(m+n) となります。空の入力、重複なし、等しい端点、点区間、包含関係、および複数の連続した交差についてテストします。
よくある間違い
- 間違い → 左端点が厳密に小さい場合にのみ出力する → 失敗する理由: 閉区間の単一点の交差が消えてしまう → 修正: 契約を確認し、等しい端点を保持する。
- 間違い → 各
A区間に対してすべてのB区間を走査する → 失敗する理由: ソートが無視され、時間がO(mn)になる → 修正: 単調なポインタを維持する。 - 間違い → 常に
iをインクリメントする → 失敗する理由:B[j]の方が先に終了する可能性があり、重複した比較や出力の取りこぼしが発生する → 修正: 終了値を比較して小さい方を進め、等しい場合は両方を進める。 - 間違い → ソートされていない入力に対して線形時間を主張する → 失敗する理由: ポインタの証明が成り立たなくなる → 修正: まず各リストをソートまたはマージする。
フォローアップの質問と回答
半開区間 [start,end) の場合は何が変わりますか？
左端点が厳密に小さいことを要求します。[1,2) と [2,4) には点の交差はありません。ポインタ移動のための終了比較は同じままで構いませんが、端点の規約を明示的に述べてください。
各リストがソートされておらず重複がある場合でも O(m+n) を維持できますか？
直接は不可能です。まず各リストをソートおよびマージし（少なくとも O(m log m+n log n) のコストがかかります）、その後に線形の2ポインタ走査を実行します。
出力が交差の合計長である必要がある場合はどうなりますか？
走査を維持し、端点の規約に合わせて調整された各 right-left を累積します。整数の閉区間の場合、数式を記述する前に、長さが幾何学的なスパンを意味するのか、含まれる点の個数を意味するのかを明確にしてください。
2つのリストが巻き戻し不可能なストリームである場合はどうなりますか？
各ストリームが開始順でソートされている限り、現在の区間と次の読み込み位置をポインタの状態として保持します。交差を出力した後、終了した区間を破棄します。順序が乱れているデータにはバッファリングと異なる設計が必要です。