C++で解く「会議室 II（Meeting Rooms II）」問題 ― 必要な会議室の最小数を求めるアルゴリズム

問題概要

会議の開始時刻と終了時刻のペアからなる区間の配列 [[s1,e1],[s2,e2],...] が与えられます。各区間は (si < ei) を満たすものとします。このとき、すべての会議を開催するために最低限必要な会議室の数を求めるのがこの問題です。

たとえば、入力が [[0, 30], [5, 10], [15, 20]] の場合、出力は 2 になります。[0, 30] の会議が進行している間に [5, 10] と [15, 20] の会議が行われるため、もう 1 つの会議室が必要になるからです。

解法のアプローチ

この問題は優先度付きキュー（priority queue）を使うと効率的に解けます。進行中の会議の終了時刻を管理し、新しい会議の開始前に終了済みの会議を取り除いていくことで、同時に必要となる会議室の最大数を求められます。手順は以下の通りです。

• 優先度付きキュー pq を用意する（終了時刻が最も早い会議を先頭に取り出せるようにする）
• 区間の配列を開始時刻順にソートする
• 答えを格納する変数 ret を 0 で初期化する
• i を 0 から区間の個数未満まで 1 ずつ増やしながら、以下を繰り返す
  • pq が空でなく、pq の先頭にある会議の終了時刻が intervals[i][0]（現在の会議の開始時刻）以下である間、pq から要素を削除する
  • intervals[i] を pq に挿入する
  • ret を max(ret, pq のサイズ) で更新する
• 最後に ret を返す

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

// 終了時刻が早い会議ほど先に取り出される比較器（最小ヒープ）
struct Comparator {
    bool operator()(vector<int>& a, vector<int>& b) {
        return a[1] > b[1];
    }
};

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        // 進行中の会議を管理する優先度付きキュー
        priority_queue<vector<int>, vector<vector<int>>, Comparator> pq;
        // 開始時刻順にソート
        sort(intervals.begin(), intervals.end());
        int ret = 0;
        for (int i = 0; i < intervals.size(); i++) {
            // 現在の会議の開始までに終了した会議をキューから除去
            while (!pq.empty() && pq.top()[1] <= intervals[i][0])
                pq.pop();
            pq.push(intervals[i]);
            ret = max(ret, (int)pq.size());
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{0, 30}, {5, 10}, {15, 20}};
    Solution ob;
    cout << ob.minMeetingRooms(v);
}

入力と出力

入力：

{{0, 30}, {5, 10}, {15, 20}}

出力：

2

動作のポイント

このアルゴリズムの鍵は、pq のサイズが「その時点で同時に進行している会議の数」を表していることです。会議を開始時刻順に処理し、すでに終了した会議をキューから取り除くことで、常にアクティブな会議だけがキューに残ります。そのため、キューサイズの最大値が求めるべき会議室の最小数となります。

また、ある会議の終了時刻と別の会議の開始時刻が一致する場合（例：t 時に終わる会議と t 時に始まる会議）、このコードでは条件が <= になっているため、同じ会議室を再利用できるものとして扱います。

計算量

ソートに O(n log n) かかり、各会議はキューへの挿入・削除がそれぞれ高々 1 回ずつであるため、全体の時間計算量は O(n log n) です。空間計算量は、キューに最大 n 個の会議が格納され得るため O(n) となります。