JavaScriptで身長に基づいてキューを再構築するアルゴリズム

ランダムな順番で並んでいる人々の一覧があるとします。各人は整数のペア (h, k) で表されます。ここで h はその人の身長、k は「その人より前に立っている、身長が h 以上である人の数」を意味します。

本記事では、与えられた情報をもとに元のキュー（整列）を再構築するアルゴリズムをJavaScriptで実装します。

注： 人数は1,100人未満であるものとします。

入力例

const arr = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]];

この場合、期待される出力（再構築されたキュー）は次のようになります。

const output = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]];

アプローチ

この問題を効率よく解くポイントは、次の2つのステップです。

1. 身長の降順でソートする。 身長が同じ場合は、k の値が小さい順（昇順）に並べます。
2. 先頭から順に、各人を結果配列のインデックス k の位置へ挿入する。

身長の高い人から順に挿入していけば、挿入の時点で列の中に既にいるのは必ず「自分と同じかそれより背の高い人」だけです。そのため、k 番目の位置に挿入すれば「前方に身長 h 以上の人がちょうど k 人いる」という条件が自動的に満たされます。また、同じ身長の人同士では k の小さい方を先に挿入しないと相対的な順序が崩れてしまうため、ソート時に k の昇順も指定しておく必要があります。

実装コード

const arr = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]];

const reconstructQueue = data => {
    const result = [];
    // 身長の降順、同一身長なら k の昇順でソート
    const sorter = (a, b) => {
        return b[0] - a[0] || a[1] - b[1];
    };
    data.sort(sorter);
    // 各人を k 番目の位置に挿入
    for (let i = 0; i < data.length; i++) {
        result.splice(data[i][1], 0, data[i]);
    }
    return result;
};

console.log(reconstructQueue(arr));

出力

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

[ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 4, 4 ], [ 7, 1 ] ]

計算量

ソートに O(n log n)、さらに挿入処理では各要素に対して最大 O(n) の splice が必要となるため、全体の計算量は O(n²) です。ただし人数が1,100人未満という制約のもとでは十分に高速に動作し、実用上まったく問題ありません。