JavaScriptでソート済みの区間配列に新しい区間を挿入する方法

区間とは何か

この記事では、「区間（インターバル）」を、2つの数値からなる配列のうち、最初の数値が必ず2番目の数値よりも小さいものとして定義します。

例えば、以下はすべて有効な区間です。

[4, 6], [2, 3], [6, 8], [2, 7], [1, 8]

問題の概要

ここで、各区間の開始時刻（各区間の最初の要素）に基づいてソートされた区間の配列があると仮定します。

さらに、この配列内の区間は互いに重なり合っていないものとします。つまり、隣り合う任意の2つの区間については、次の関係が常に成り立ちます。

[m, n], [x, y] のとき
m < n < x < y

したがって、条件を満たす区間配列の一例は次のようになります。

const arr = [[2, 4], [5, 7], [9, 10], [13, 17]];

今回求められているのは、このようなソート済みの区間配列を第1引数に、挿入したい単一の区間を第2引数として受け取るJavaScript関数を作成することです。

関数は、指定された区間を配列内の正しい位置に挿入しつつ、配列内の区間同士が重ならないという性質（非重複性）を維持しなければなりません。

必要であれば、非重複性を保つために、既存の2つ以上の区間をマージ（統合）しても構いません。

例えば、先ほどの区間配列に対して [6, 13] を挿入する場合、期待される出力は次のとおりです。

const output = [[2, 4], [5, 17]];

実装コード

以下が実際のコード例です。

const arr = [[2, 4], [5, 7], [9, 10], [13, 17]];
const interval = [6, 13];
const insertWithin = (arr = [], interval = []) => {
   const res = [];
   let ind = 0;
   while (arr[ind] && arr[ind][1] < interval[0]) {
      res.push(arr[ind]);
      ++ind;
   };
   let start = interval[0];
   let end = interval[1];
   while (arr[ind] && arr[ind][0] <= interval[1]) {
      start = Math.min(start, arr[ind][0]);
      end = Math.max(end, arr[ind][1]);
      ++ind;
   }
   res.push([start, end]);
   while (arr[ind]) {
      res.push(arr[ind]);
      ++ind;
   }
   return res;
};
console.log(insertWithin(arr, interval));

コードの解説

このアルゴリズムは、大きく分けて3つのステップで動作します。

ステップ1：挿入位置より前の区間をコピー
最初のwhileループでは、新しい区間の開始位置よりも前に完全に存在する区間（終了位置が新しい区間の開始位置未満である区間）を、そのまま結果配列に追加していきます。

ステップ2：重なる区間をマージ
次のwhileループでは、新しい区間と重なる可能性のある区間を走査し、それらの最小の開始位置と最大の終了位置を求めることで、すべてを1つの区間に統合します。

ステップ3：残りの区間をコピー
最後に、マージ対象とならなかった残りの区間をそのまま結果配列へ追加し、完成した配列を返します。

このアプローチにより、配列は一度も逆順にすることなく、線形時間 O(n) で処理が完了します。

出力結果

コンソールには次のように出力されます。

[[2, 4], [5, 17]]