Back to solutions

Meeting Rooms II

MediumGreedy

Given meeting time intervals, return the minimum number of conference rooms required.

Open problem
Constraints
  • 1 <= intervals.length <= 10^4
  • intervals[i] = [start, end]

Min-heap of end times

Time O(n log n)Space O(n)

Sort meetings by start. Use a min-heap of end times; for each meeting, free a room if its earliest end is not later than the new start, then add this meeting's end. The peak heap size is the answer.

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

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> ends;
    for (auto& iv : intervals) {
        if (!ends.empty() && ends.top() <= iv[0]) ends.pop();
        ends.push(iv[1]);
    }
    return ends.size();
}