問題の要件と使用例
未ソートの配列 intervals が与えられます。各要素は整数の時間区間 [start, end) であり、start は含まれ、end は除外されます。したがって、時刻 t に終了する会議は、t に開始する別の会議のために部屋を解放します。0 <= intervals.length <= 100000 および 0 <= start < end <= 1000000000 であると仮定します。すべての会議をスケジュールするのに必要な最小の会議室数を返してください。
例えば、[[0, 30], [5, 10], [15, 20]] は 2 を返し、[[1, 5], [5, 8]] は 1 を返し、空の配列は 0 を返します。これらは本記事で採用している面接の制約であり、特定のプラットフォームに起因する隠れた制限ではありません。
公開資料には、いくつかの代表的な証拠が存在します。PracHub は2026年に同様の問題設定を更新しました。interviewing.io は、会議室の最小数問題をタイムラインまたは優先度付きキューで解決可能な区間問題として紹介しています。2026年2月の公開面接体験記の1つには、2つのポインタ、優先度付きキュー、および有界な時間領域に対する配列に関する発展質問が記録されています。UMass のアルゴリズム講義ノートには、区間分割（interval-partitioning）の中核となる証明が記載されています。すなわち、区間を開始時刻順に処理する場合、貪欲アルゴリズムによって使用される部屋数は最大重複深度と等しくなります。単一の体験談はその候補者の経験を証明するに過ぎないため、本記事は一般的な面接頻度を推測したり、この問題を特定企業の固定問題集に帰属させたりするものではありません。
面接官の評価基準
第1の評価ポイントはモデリングです。これはリソースのカウント問題であり、区間のマージや互換性のある最大部分集合の選択ではありません。最小の部屋数は、任意の瞬間において進行中の会議の最大数（区間集合の「深さ（depth）」と呼ばれることが多い）と等しくなります。
第2の評価ポイントは端点のセマンティクスです。半開区間では、同じ時刻における開始イベントよりも前に終了イベントを処理しなければなりません。start === end を重複として扱うと、[1, 5) と [5, 8) に誤って2部屋を割り当てることになります。
第3の評価ポイントは不変条件と証明です。開始時刻と終了時刻を別々にソートすると、ポインタはどの終了時刻がどの会議に属しているかを保持しなくなります。同時使用数のみが問題となる場合、なぜ個々の会議の識別情報が無関係であるのかを説明できる必要があります。次のイベントが残りの最も早い開始であるか終了であるかを知るだけで十分です。
最後に、面接官は要件変更時におけるデータ構造の選択をテストできます。2つの配列による走査はカウントを直接返します。具体的な部屋の割り当て、各会議で使用される部屋、または再利用履歴が求められる場合は、終了時刻と部屋識別子の両方を保持する最小ヒープ（min-heap）が必要になります。
回答前に明確にすべき質問
- 区間は
[start, end)ですか、それとも閉区間ですか？ この問題では半開区間を使用するため、端点が等しい場合は競合しません。 - 長さが0の会議は有効ですか？ この仕様では
start < endを要求し、[t, t)を拒否します。ビジネス要件で許可される場合は、それらがリソースを消費するかどうかを定義してください。 - 空の入力は何を返すべきですか？ 最初の会議の初期化エラーを避けるため、
0を返します。 - 返すのはカウントのみですか、それとも割り当てもですか？ カウントだけであれば2つの配列で十分です。割り当てを行うには会議の識別情報と再利用可能な部屋を保持する必要があります。
- 実装が入力を変更（破壊）してもよいですか？ 以下の実装では開始値と終了値をコピーし、呼び出し元の配列には手を加えません。
- 時刻は安全な整数（safe integer）の範囲内ですか？ 提示された上限は JavaScript の安全な整数範囲内に収まります。より大きなタイムスタンプには新たな表現の取り決めが必要です。
- 入力が無効な場合はありますか？ 面接の入力は通常、仕様を満たしています。本番環境のバリデーションは、中核となるアルゴリズム内ではなくシステムの境界で行うべきです。
30秒の回答フレームワーク
「まず区間が半開区間であることを確認します。これにより、ある時刻に解放された部屋は直ちに再利用できます。最小カウントのみが必要な場合は、開始時刻と終了時刻を別々にソートし、2つのポインタで走査します。次の開始時刻が最も早い終了時刻より厳密に早い場合は使用部屋数を増やし、そうでなければ先に部屋を解放します。そして最大使用数を保持します。
その最大値は下限であると同時に達成可能です。同時並行の会議には別々の部屋が必要であり、開始時刻順に処理することで、既存の部屋がすべて使用中である場合にのみ新しい部屋を開くからです。ソートにより全体の計算量は O(n log n) 時間、追加空間量は O(n) となります。発展課題で具体的な割り当てを求められた場合は、終了時刻と部屋識別子を保持する最小ヒープを使用します。」
ステップ別の解説
ステップ1: ソートされた2つのイベントストリームから最大使用数を計算する
すべての開始時刻を昇順で starts に、すべての終了時刻を昇順で ends に格納します。startIndex は次に処理する未処理の開始イベントを指し、endIndex は次に処理する未処理の終了イベントを指します。roomsInUse は、現在の走査位置の直後において依然として占有されている部屋数です。有効な区間は start < end を満たすため、走査においてアクティブな会議が存在しない状態で終了イベントが処理されることはありません。
starts[startIndex] < ends[endIndex] の場合、次のイベントは開始です。使用数を増やし、最大値を更新します。そうでない場合は、先に終了を処理して部屋を1つ解放します。厳密な小なり比較（<）は意図的なものです。等しい端点は次の開始の前に解放分岐を通るため、[start, end) を正確に実現します。
export function minimumMeetingRooms(
intervals: ReadonlyArray<readonly [number, number]>,
): number {
if (intervals.length === 0) return 0
const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)
let startIndex = 0
let endIndex = 0
let roomsInUse = 0
let maximumRooms = 0
while (startIndex < intervals.length) {
if (starts[startIndex] < ends[endIndex]) {
roomsInUse += 1
maximumRooms = Math.max(maximumRooms, roomsInUse)
startIndex += 1
} else {
roomsInUse -= 1
endIndex += 1
}
}
return maximumRooms
}[[0, 30], [5, 10], [15, 20]] をトレースします。開始時刻は 0, 5, 15、終了時刻は 10, 20, 30 です。0 と 5 の開始により、使用数は0から2に増加します。10 の終了で部屋が1つ解放され、1に減少します。15 の開始で再び2に増加します。最大値は2です。
ステップ2: 最大値が最適解であることを証明する
まず、走査によるカウントが正しいことを示します。各 [start, end) を +1 の開始イベントと -1 の終了イベントとして表現し、時刻順にソートし、同時刻の場合は終了を開始より前に処理します。任意のイベントの直後において、累積和はその直後のタイムラインをカバーしている区間の数と等しくなり、これはまさに占有されている部屋の数です。ポインタを用いて2つのソート済み配列をマージ走査することで、すべてのイベントがその順序で処理されます。
次に、この最大値が最適であることを証明します。最大の重複深度を d とします。ある瞬間において d 個の会議が同時に進行するため、いかなるスケジュールでも少なくとも d 個の部屋が必要です。これが下限となります。会議を開始時刻順に処理する場合、貪欲な割り当てでは既存のすべての部屋がまだ終了していない会議で占有されている場合にのみ新しい部屋を開きます。部屋 k を開く場合、その新しい会議と他の k - 1 個の会議がその瞬間に共存しているため、k <= d が成り立ちます。したがって、d 個の部屋のみを使用するスケジュールが存在します。実現可能な上限が下限と一致するため、最小値は d であり、これは走査によって返される最大値と正確に一致します。
配列の構築には O(n)、2回のソートには O(n log n)、マージ走査には O(n) のコストがかかります。全体の計算量は O(n log n) 時間、追加空間量は O(n) です。時刻が小さく固定された離散領域から得られる場合、階差配列（difference array）を用いることでこれを O(n + U) 時間および O(U) 空間に置き換えることができます。ただし、時間の上限が10億である場合、この最適化は適していません。
ステップ3: 要件変更に応じてヒープまたは階差配列を選択する
別の解法として、会議を開始時刻順にソートし、使用中の各部屋の終了時刻を最小ヒープで管理する方法があります。会議を処理する前に、end <= start であるすべてのエントリをポップし、その後に新しい終了時刻をプッシュします。ヒープの最大サイズが答えとなります。これも O(n log n) 時間、最悪ケースで O(n) 空間を要します。
カウントを求めるだけであれば走査法の方が短く、同時刻のイベントにおいて終了が開始より優先されるというルールも明確になります。ヒープは拡張時に威力を発揮します。各エントリを end から { end, roomId } に変更します。利用可能な部屋識別子の2つ目の最小ヒープを保持し、会議終了後に識別子を回収して、各元の会議インデックスを具体的な部屋にマッピングします。番号が最も小さい利用可能な部屋を選択するという要件がある場合、最も早い終了時刻だけで選択するのは不十分であり、使用中の部屋と利用可能な部屋を別々に管理する必要があります。
動的なオンライン予約は異なる問題です。将来の会議が個別に追加され、キャンセルされる可能性がある場合、すべての区間を繰り返しソートするのはコストが高すぎる可能性があります。クエリのワークロードによっては、順序付きイベントストア、区間木（interval tree）、またはカレンダーインデックスが必要になる場合があります。O(n log n) のオフライン配列による回答を、完全なオンラインシステム設計として提示すべきではありません。
質の高い模範解答
「[start, end) の前提で解きますので、一方の終了時刻と他方の開始時刻が等しい場合は部屋を再利用できます。全ペアの競合チェックもベースラインとしては有効ですが、最悪ケースで O(n^2) のコストがかかります。最大10万件の会議に対応するため、イベントをソートする手法を取ります。
ソートされた開始配列と終了配列を作成します。2つのポインタで次のイベントを決定します。開始の方が早ければ現在の使用数を増やして最大値を更新し、終了の方が早いか同時であれば先に部屋数を減らします。[[0, 30], [5, 10], [15, 20]] の場合、使用数は 1, 2, 1, 2 と推移するため、答えは 2 となります。
正当性には2つの要素があります。走査中の累積カウントはアクティブな区間の数に等しいため、その最大値は重複深度 d になります。それらの会議が共存する以上、いかなるスケジュールでも少なくとも d 個の部屋が必要です。開始時刻順の貪欲割り当ては、既存の部屋がすべて使用中である場合にのみ部屋を追加するため、d を超えて部屋を使用することはありません。したがってこのアルゴリズムは最適です。計算量は O(n log n) 時間、空間量は O(n) です。各会議の部屋識別子が必要な場合は、元のインデックスを保持し、終了時刻ヒープと利用可能識別子ヒープを併用して部屋を割り当てます。」
よくある間違い
- 間違い: 区間のマージ問題を解いてしまう。失敗の理由: マージされた区間の数は、最大並行使用数を表しません。修正: 開始イベントと終了イベントを走査し、アクティブ数の最大値を保持します。
- 間違い: 端点が等しい場合に終了より先に開始を処理してしまう。失敗の理由: 直ちに再利用可能な部屋が2重にカウントされます。修正: 半開区間の仕様に基づき、終了イベントを優先します。
- 間違い: JavaScript のデフォルトのソートを使用してしまう。失敗の理由: 辞書順ソートにより
10が2より前に配置されます。修正: 明示的に(a, b) => a - bを渡します。 - 間違い: 最終的な
roomsInUseを返してしまう。失敗の理由: 最終的な使用数は過去の最大値より少なくなる場合があります。修正: 開始イベントごとにmaximumRoomsを更新します。 - 間違い: 会議のすべてのペアを比較してしまう。失敗の理由: 最悪ケースの時間計算量が
O(n^2)になります。修正: 2つのイベントストリームをソートし、線形にマージします。 - 間違い: 割り当てを生成する際に、終了した会議を1つしかポップしない。失敗の理由: 使用中および利用可能な集合が不完全になります。修正:
end <= startであるすべての部屋をポップし、再利用可能な識別子を個別に管理します。 - 間違い: 区間の境界を未定義のままにする。失敗の理由: 端点が等しいケースでテスト結果が食い違います。修正: コーディング前に半開区間か閉区間か、および同時発生イベントの優先度を定義します。
- 間違い: 公開問題集のタグから企業の出題実績を断定してしまう。失敗の理由: サードパーティのタグや1件の体験談は、企業の固定的な出題を証明するものではありません。修正: 証拠が不十分な場合は
companyNameをnullのまま保ち、各情報源が裏付けている事実のみを述べます。
発展質問と回答
なぜ2つのソート済み配列で会議の対応関係を破棄してもよいのですか？
目的は各瞬間におけるアクティブな会議数を把握することだけに依存しているためです。カウントの次の変化は、その終了がどの会議のものであるかに関わらず、未処理の最も早い開始と最も早い終了によって決まります。割り当てや会議ごとの追跡を行う場合は再び対応関係が必要になるため、それらの要件には会議インデックスと部屋識別子を含むヒープを使用します。
閉区間 [start, end] の場合は何が変わりますか？
同じ時刻における終了と開始が競合します。比較処理では開始を先に処理し、start <= end の場合に使用数を増やす必要があります。演算子を機械的に変更するよりも、同時刻の優先度を明示的に定義する方が安全な説明となります。
各会議の部屋識別子を返すにはどうすればよいですか？
元のインデックスを保持し、開始時刻順にソートします。使用中の部屋を { end, roomId } の最小ヒープで管理します。各会議の前に、end <= start であるすべての部屋を利用可能識別子の最小ヒープに移動します。利用可能な最小の識別子を再利用するか、新しい識別子を作成して、assignment[originalIndex] = roomId を記録します。
なぜ最小の部屋数が最大の重複深度と等しくなるのですか？
同時に進行する会議は部屋を共有できないため、最大の重複深度は避けられない下限です。開始時刻順の貪欲アルゴリズムは、既存の部屋がすべて占有されている場合にのみ部屋を開きます。したがって、開かれる各部屋はその瞬間に重複している同数の会議に対応しており、下限を超えることはありません。両者が一致することが最適性を証明しています。
どのようなエッジケースをテストすべきですか？
最低限、空の配列、1つの区間、重複なし、完全な重複、連続して等しい端点、同一の開始時刻、同一の終了時刻、重複した区間、逆順にソートされた入力、およびサイズ上限付近のランダムデータをテストすべきです。ランダムな差分テストをサポートするために小さな O(n^2) や離散イベントオラクルを利用できますが、使い捨ての検証コードを本番用の実装に混入させるべきではありません。
時間領域が小さい場合、線形時間の解法は可能ですか？
可能です。時間領域 U に比例したサイズの階差配列を使用し、各開始時刻で1を加算し、各終了時刻で1を減算して、累積和の最大値を取得します。この計算量は O(n + U) 時間および O(U) 空間です。これは U が小さくメモリが制御されている場合にのみ価値があります。現在提示されている10億の上限のもとではソートを行う方が安全です。