JavaScriptで解く会議室スケジューリング問題 ― 時間の重複を検出する方法

問題の概要

ここでは、配列の中にさらに配列が格納されたデータ構造を扱います。各サブ配列は必ず2つの要素で構成されており、それぞれ会議の開始時刻と終了時刻を表しています。

私たちの関数に課せられたタスクは、1人の人が時間のコンフリクト（重複）を避けて出席できる会議を判定することです。具体的には、与えられたすべての会議に時間の重なりなく出席できる場合はtrue、そうでなければfalseを返します。

例として、会議の時刻を表す入力配列が次の場合を考えてみましょう。

const arr = [[5, 40], [10, 20], [25, 35]];

この場合、出力は次のようになります。

const output = false;

[5, 40]の会議が他の2つの会議（[10, 20]と[25, 35]）と時間的に重なっているため、3つすべてに出席することは不可能です。ただし、[10, 20]と[25, 35]は互いに重ならないため、この2つであればどちらにも出席できます。

実装コード

この問題に対するコードは以下の通りです。

const arr = [[5, 40], [10, 20], [25, 35]];
const canAttendAll = (arr = []) => {
    const times = new Set();
    const { length } = arr;
    for (let i = 0; i < length; i += 1) {
        for (let j = arr[i][0]; j < arr[i][1]; j += 1) {
            if (times.has(j)) {
                return false;
            } else {
                times.add(j);
            };
        };
    };
    return true;
};
console.log(canAttendAll(arr));

コードの仕組み

このアルゴリズムは、Set（セット）オブジェクトを利用したシンプルなアプローチです。

• まず、空のSet times を用意し、すでに使用済みとなった時間スロットを記録していきます。
• 外側のループで各会議を取り上げ、内側のループでその会議の開始時刻から終了時刻までの各時刻を1つずつ確認します。
• ある時刻がすでにSetに登録されている場合、それは別の会議と時間が重複していることを意味するため、直ちに false を返します。
• 重複が見つからなければ、その時刻をSetに追加して処理を続行します。
• すべての会議を矛盾なく処理できた場合は、最後に true を返します。

出力結果

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

false

補足：計算量と実用上の注意点

この実装は理解しやすい反面、時刻が整数値であることを前提としており、会議の長さに比例して内側のループが回るため、時間範囲が大きいケースでは非効率になる可能性があります。

実際の開発では、会議を開始時刻順にソートして隣接する会議同士の終了時刻と開始時刻を比較する方法や、インターバルスケジューリングのアルゴリズムを活用することで、より効率的かつ柔軟に処理できます。