56. Meeting Rooms II

読了目安約2分

その他 / LeetCode 253 (Medium) — すべての会議を開くのに必要な会議室の最小数

この章の目次

問題

LeetCode 253. Meeting Rooms II（Medium / カテゴリ: その他）

会議の時刻を並べた配列 intervals が与えられます。形式は 55. Meeting Rooms と同じで、各要素が [開始, 終了] を表します。今回は重なった会議を別の部屋で開くとして、必要な会議室の最小数を返します。

答えは「同時に開かれている会議の数」の最大値と一致します。例: [[0, 30], [5, 10], [15, 20]] は時刻 5 から 10 の間に 2 つの会議が同時に開かれるので 2 です。 [[7, 10], [2, 4]] は重なりがないので 1 で、終了と同時に始まる [[1, 5], [5, 8]] も部屋を使い回せるので 1 です。

この問題は LeetCode Premium 限定です。問題の要点は上の要約の通りです。無料で読める類題は 1094. Car Pooling で、「同時に重なる数の最大値」を数える点が共通です。

考え方

ヒント 1

時刻を進めながら「いま開いている会議の数」を数えられれば、その最大値が答えです。

ヒント 2

開始時刻だけの配列と終了時刻だけの配列を、別々にソートします。開始時刻を順に見て、最も早い未処理の終了時刻より前なら部屋を 1 つ増やし、そうでなければ終了済みの部屋を使い回して終了側の添字を進めます。どの開始とどの終了が同じ会議かはソートで崩れますが、同時に開いている数を数えるだけなら問題ありません。

Swift 実装のポイント

intervals.map { $0[0] }.sorted() で開始時刻だけの配列を作れます。終了時刻も同様です。
使い回しの判定は s < ends[e] です。等しいときは部屋を使い回せるので、増やしません。
優先度付きキューで使用中の部屋の終了時刻を管理する解法もありますが、Swift の標準ライブラリにはないため、2 本の配列を走査する形が書きやすいです。

模範解答

Swift
class Solution {
    func minMeetingRooms(_ intervals: [[Int]]) -> Int {
        let starts = intervals.map { $0[0] }.sorted()
        let ends = intervals.map { $0[1] }.sorted()
        var rooms = 0
        var e = 0
        for s in starts {
            if s < ends[e] {
                rooms += 1
            } else {
                e += 1
            }
        }
        return rooms
    }
}

計算量: O(n log n)。