JavaScriptで最長のペアチェーンを見つける方法

問題

数値ペア(組)の配列 arr を唯一の引数として受け取り、形成可能な最長チェーンの長さを返す JavaScript 関数を作成します。各ペアにおいて、最初の数値は必ず 2 番目の数値より小さいものとします。

ここで、ペア (c, d) が別のペア (a, b) の後に続けられるのは、b < c が成り立つ場合に限られると定義します。このルールに従ってペアの連鎖(チェーン)を形成することができ、本関数はその中で最も長いチェーンの長さを求める必要があります。

入力例

const arr = [
    [1, 2], [2, 3], [3, 4]
];

出力例

const output = 2;

出力の説明

最長のチェーンは [1,2] → [3,4] です。[2,3] は [1,2] の直後に続けられないため(2 < 2 が成り立たない)、答えは 2 となります。

解法のアプローチ

この問題は貪欲法(グリーディ法)を使うことで効率的に解けます。手順は以下の通りです。

• すべてのペアを終了値(2番目の要素)の昇順でソートします。
• 最初のペアの終了値を現在の終了位置として記録し、カウントを 1 に初期化します。
• 残りのペアを順に走査し、開始値が現在の終了値より大きければ、そのペアをチェーンに追加して終了値とカウントを更新します。

終了値が小さいペアから優先的に選ぶことで、後続のペアがチェーンに参加できる可能性を最大限に保てるため、この貪欲な選択が最適解をもたらします。計算量はソートに伴う O(n log n) であり、動的計画法を用いる O(n²) よりも高速です。

実装例

const arr = [
    [1, 2], [2, 3], [3, 4]
];
const findLongestChain = (arr = []) => {
    // 終了値で昇順にソート
    arr.sort(([, b], [, d]) => b - d);
    let currentEnd = arr[0][1];
    let count = 1;
    for (const [start, end] of arr) {
        if (start > currentEnd) {
            count += 1;
            currentEnd = end;
        }
    }
    return count;
};
console.log(findLongestChain(arr));

出力結果

2

まとめ

ペアを終了値でソートして貪欲に選択するだけで、O(n log n) の計算量で最長チェーンの長さを求められます。これは区間スケジューリング問題と同じ発想なので、会議室の予約やタスクの割り当てなど、類似の問題にも応用できる有用なテクニックです。