JavaScriptで2つの区間配列の共通部分を求める方法【2ポインタ法】

問題概要

本記事では、2つの区間（インターバル）配列を受け取り、その共通部分を返すJavaScript関数を実装します。入力となる配列 arr1 と arr2 には以下の前提があります。

• 各区間は互いに重なり合わない（pairwise disjoint）
• 各区間はソートされた順序で格納されている

閉区間 [a, b]（a ≤ b）は、a ≤ x ≤ b を満たす実数 x の集合を表します。また、2つの閉区間の共通部分（積集合）は、空集合になるか、あるいは1つの閉区間として表現できます。例えば、[1, 3] と [2, 4] の共通部分は [2, 3] です。

入力例

const arr1 = [[0,2],[5,10],[13,23],[24,25]];
const arr2 = [[1,5],[8,12],[15,24],[25,26]];

期待される出力

const output = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]];

アプローチ：2ポインタ法

両配列がすでにソートされているため、2ポインタ（Two Pointers）法を使えば O(n + m) の時間計算量で効率的に解けます。考え方は以下のとおりです。

1. 各配列の先頭にポインタ i と j を置きます。
2. 現在注目している区間 A[i] = [a, b] と B[j] = [c, d] に対して、共通部分の下限 lo = Math.max(a, c)、上限 hi = Math.min(b, d) を計算します。
3. lo ≤ hi が成り立てば共通部分が存在するので、[lo, hi] を結果に追加します。
4. 終点が小さい側の区間のポインタを1つ進めます。こうすることで、常に「まだ終わっていない最も左側の区間」を比較対象に保てます。
5. どちらかの配列を走査し終えたら処理を終了します。

実装コード

const arr1 = [[0,2],[5,10],[13,23],[24,25]];
const arr2 = [[1,5],[8,12],[15,24],[25,26]];

const findIntersection = function (A, B) {
  const res = [];
  let i = 0;
  let j = 0;

  while (i < A.length && j < B.length) {
    const [a, b] = A[i];
    const [c, d] = B[j];

    // 共通部分の候補を計算
    const lo = Math.max(a, c);
    const hi = Math.min(b, d);

    if (lo <= hi) {
      res.push([lo, hi]);
    }

    // 終点が小さい側のポインタを進める
    if (b < d) {
      i++;
    } else {
      j++;
    }
  }

  return res;
};

console.log(findIntersection(arr1, arr2));

実行結果

[
  [ 1, 2 ],
  [ 5, 5 ],
  [ 8, 10 ],
  [ 15, 23 ],
  [ 24, 24 ],
  [ 25, 25 ]
]

出力の読み方

最初の区間ペアでは、[0, 2] と [1, 5] の共通部分が [1, 2] になります。また、[5, 10] と [1, 5] のように端点だけが接する場合は、長さ0の区間 [5, 5] として正しく検出されます。このように、点のみの共通部分も漏れなく取得できるのがこのアルゴリズムの特徴です。

まとめ

• 時間計算量：O(n + m) — 各ポインタは最大でも配列の長さ分しか進みません。
• 空間計算量：O(1)（出力を除く）— 結果配列以外に追加のメモリは不要です。
• 実装のポイント：ソート済み・非重複という前提があるため、事前のマージやソートが不要で、シンプルなループだけで実装できます。