JavaScriptで他の区間に包含される区間を削除するアルゴリズム

問題概要

JavaScriptで、2次元配列 arr を唯一の引数として受け取る関数を作成します。

入力配列の各サブ配列は、必ず2つの数値から構成され、それぞれ時間区間（インターバル）を表しています。

この関数では、配列 arr 内で他の区間によって完全に包含されている区間をすべて削除する必要があります。区間 [a, b) が区間 [c, d) に包含されるとは、c <= a かつ b <= d が成り立つ場合を指します。最終的に、削除後に残った区間の数を返します。

入力例

const arr = [
    [2, 5],
    [5, 7],
    [3, 9]
];

出力例

const output = 2;

出力の解説

区間 [5, 7] は区間 [3, 9] に完全に包含されているため、削除されます。その結果、残る区間は [2, 5] と [3, 9] の2つとなり、出力は 2 になります。

解決アプローチ

この問題を効率的に解くには、以下の手順で処理を行います。

1. まず、各区間を開始位置の昇順でソートします。開始位置が同じ場合は、終了位置の降順でソートします。
2. ソート後、隣接する区間を順番に比較し、現在の区間が直前の区間に包含されているかどうかを判定します。
3. 包含されている場合はカウントを1減らし、そうでなければ比較基準となる区間を更新します。

この手法により、計算量 O(n log n)（ソートのコスト）で問題を解くことができます。

実装コード

実際のコードは以下の通りです。

const arr = [
    [2, 5],
    [5, 7],
    [3, 9]
];
const removeCovered = (arr = []) => {
    arr.sort(([a, b], [c, d]) => (a === c ? d - b : a - c));
    let last = arr[0];
    let count = arr.length;
    for(let i = 1; i < arr.length; i++){
        const [a, b] = last;
        const [c, d] = arr[i];
        if(c >= a && d <= b){
            count -= 1;
        }else{
            last = arr[i];
        };
    };
    return count;
};
console.log(removeCovered(arr));

実行結果

コンソールに出力される結果は以下の通りです。

2

コードのポイント解説

• ソートの条件： a === c ? d - b : a - c の部分により、開始位置が同じ区間同士では終了位置が大きい方を先に配置しています。これにより、同一開始位置の複数区間があっても包含判定を見逃しません。
• 変数 last： 現時点で「まだ包含されていない」と判断された最新の区間を保持します。次の区間との比較基準として使われます。
• 変数 count： 最初に全区間数を設定し、包含されている区間が見つかるたびに1ずつ減算することで、残存区間数を求めています。