Meeting Rooms II

57.7k
0

Given an array intervals, where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time is exclusive, so a room becomes available for another meeting beginning at the same time.

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: Meeting [0,30] overlaps with both shorter meetings. Meetings [5,10] and [15,20] can share a second room.

Example 2

Input: intervals = [[0,8],[8,10]]
Output: 1
Explanation: Meeting [0,8] releases the room exactly at time 8, allowing meeting [8,10] to use the same room.

Brute Force Approach

The required room count reaches a new peak only at a meeting start time. Counting all active meetings at every start time therefore reveals the largest overlap without checking every possible clock value.

For a chosen start time, an active interval has already started but has not yet ended. The largest active count across all meeting starts becomes the answer.

Algorithm

  • Begin with maximumRooms = 0, so the largest overlap can be recorded as every meeting start is examined.

  • Select each meeting start time because room demand can rise only at a new start.

  • Reset currentRooms = 0 for the selected time because every overlap count belongs to one independent time point.

  • Scan every interval and count an interval only when start <= time < end, preserving the exclusive end-time rule.

  • Compare currentRooms with maximumRooms after the full scan because the completed count represents all simultaneous meetings at the selected time.

  • Repeat the scan for every meeting start because any maximum overlap must begin at a meeting start.

  • Return maximumRooms because the greatest simultaneous overlap equals the minimum number of rooms.

Dry Run

meeting-rooms-ii-brute-approach

meeting-rooms-ii-brute-approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the minimum room count by direct overlap checks.
int minMeetingRooms(vector<vector<int>>& intervals) {
int maximumRooms = 0;
// Test every point capable of increasing overlap.
for (int i = 0; i < intervals.size(); i++) {
int time = intervals[i][0];
int currentRooms = 0;
// Count meetings active at the selected start.
for (int j = 0; j < intervals.size(); j++) {
// An exclusive end releases the room on equality.
if (intervals[j][0] <= time &&
time < intervals[j][1]) {
currentRooms++;
}
}
// Preserve the greatest simultaneous meeting count.
maximumRooms = max(maximumRooms, currentRooms);
}
return maximumRooms;
}
};
// Driver code
int main() {
vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
Solution obj;
cout << obj.minMeetingRooms(intervals) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of intervals, because each of the N start times may require scanning all N intervals.

Space Complexity: O(1), because only a few counters and the selected start time use auxiliary space.

Better Approach

The direct method repeats overlap checks. Sorting meetings by start time removes repeated checks, while a min-heap stores the end times of meetings that are currently occupying rooms. The smallest heap value always represents the meeting that will finish first.

Before a new meeting begins, remove every end time less than or equal to its start time, because those meetings have already ended and their rooms are available again. Then add the current meeting’s end time to the heap. The maximum heap size seen during the process gives the largest number of meetings running at the same time.

Algorithm

  • Handle an empty interval list first because no meeting requires a room.

  • Sort all intervals by start time, allowing meetings to be processed in chronological order.

  • Keep a min-heap of end times of meetings currently occupying rooms, because the smallest end time identifies the meeting that finishes first.

  • Remove every heap value less than or equal to the current start time, because those meetings have already ended and their rooms are free.

  • Push the current meeting’s end time into the heap, because this meeting is now occupying a room.

  • Update maximumRooms using the heap size, because the heap contains the end times of all meetings currently occupying rooms.

  • Return maximumRooms, because the maximum number of simultaneously active meetings equals the minimum number of rooms required.

Dry Run

meeting-rooms-ii-better-approach

meeting-rooms-ii-better-approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the minimum room count with a min-heap.
int minMeetingRooms(vector<vector<int>>& intervals) {
// No meeting requires no room.
if (intervals.empty()) {
return 0;
}
// Process meetings in chronological start order.
sort(intervals.begin(), intervals.end());
// Store end times for meetings still in progress.
priority_queue<int, vector<int>, greater<int>> endTimes;
int maximumRooms = 0;
// Visit every meeting at the meeting start time.
for (vector<int>& interval : intervals) {
// Completed meetings release all reusable rooms.
while (!endTimes.empty() &&
endTimes.top() <= interval[0]) {
endTimes.pop();
}
// The current meeting occupies a room until its end.
endTimes.push(interval[1]);
// Heap size equals the current occupied room count.
int currentRooms = endTimes.size();
maximumRooms = max(maximumRooms, currentRooms);
}
return maximumRooms;
}
};
// Driver code
int main() {
vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
Solution obj;
cout << obj.minMeetingRooms(intervals) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of meetings, because sorting takes O(N log N) and each meeting end is inserted into and removed from the min-heap at most once.

Space Complexity: O(N), because the min-heap can store up to N meeting end times when all meetings overlap.

Optimal Approach

The min-heap stores individual meeting end times, but we only need to know when the next meeting starts and when the next occupied room becomes free. By sorting all start times and end times separately, these events can be processed directly.

At every step, startIndex points to the earliest unprocessed meeting start, while endIndex points to the earliest unprocessed meeting end. Comparing them tells us whether a new room is required or an existing room can be reused. The maximum number of simultaneously active meetings gives the minimum number of rooms needed.

Algorithm

  • Handle an empty interval list first, because no meeting requires a room.

  • Store all meeting start times in one array and all end times in another.

  • Sort both arrays so events can be processed in chronological order.

  • Initialize startIndex and endIndex to 0.

    • startIndex tracks the earliest meeting that has not started yet.

    • endIndex tracks the earliest meeting that has not ended yet.

  • While unprocessed meeting starts remain, compare starts[startIndex] with ends[endIndex].

    • If starts[startIndex] < ends[endIndex], a new meeting starts before any current meeting ends.

      • Increase currentRooms.

      • Update maximumRooms.

      • Move startIndex forward.

    • Otherwise, a meeting ends before or exactly when the next meeting starts.

      • Decrease currentRooms because that room becomes available for reuse.

      • Move endIndex forward.

  • Return maximumRooms, because it represents the largest number of meetings running at the same time.

Dry Run

meeting-rooms-ii optimal

meeting-rooms-ii optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the minimum room count with two pointers.
int minMeetingRooms(vector<vector<int>>& intervals) {
// No meeting requires no room.
if (intervals.empty()) {
return 0;
}
vector<int> starts;
vector<int> ends;
// Separate event types for independent ordering.
for (vector<int>& interval : intervals) {
starts.push_back(interval[0]);
ends.push_back(interval[1]);
}
// Place every start and end in chronological order.
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int startIndex = 0;
int endIndex = 0;
int currentRooms = 0;
int maximumRooms = 0;
// Process starts until every meeting has begun.
while (startIndex < starts.size()) {
// An earlier start needs another occupied room.
if (starts[startIndex] < ends[endIndex]) {
currentRooms++;
maximumRooms = max(maximumRooms, currentRooms);
startIndex++;
} else {
// An end on a tie releases a reusable room first.
currentRooms--;
endIndex++;
}
}
return maximumRooms;
}
};
// Driver code
int main() {
vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
Solution obj;
cout << obj.minMeetingRooms(intervals) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of meetings, because sorting the start and end time arrays takes O(N log N), while the two-pointer sweep takes O(N).

Space Complexity: O(N), because the separate start and end arrays together store 2N values, which simplifies to O(N).

Interview follow-up Questions

Yes. For example, if one meeting is [0,8] and another is [8,10], the first meeting frees the room at time 8. The second meeting can start in the same room at time 8, so only one room is needed.

Heap

Read Similar Blogs

Heap

Merge K Sorted Linked Lists

Given an array lists containing the heads of k singly linked lists, merge every node into one linked list sorted in non-decreasing order. Every input list is already sorted in non-decreasing order....

92.2k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on...

72.8k
Heap

Minimum Cost to Hire K Workers

Two integer arrays, quality and wage , describe n workers. Values at the same array index represent one worker's quality and minimum acceptable pay. Hire exactly k workers. Every hired worker must...

77.7k
Comments0