Meeting Rooms Problem Minimum Rooms Required in DSA C++

Mental Model

We want to find the smallest number of rooms needed so that no meetings overlap in the same room.

Analogy: Imagine you have several appointments and only a few rooms. You want to know how many rooms you need so that no two appointments happen in the same room at the same time.

Meetings timeline:
[1,4]  [2,5]  [7,9]
Rooms needed:
Room1: [1,4] -> [7,9]
Room2:    [2,5]

Dry Run Walkthrough

Input: meetings: [[1,4], [2,5], [7,9]]

Goal: Find the minimum number of rooms needed so no meetings overlap in the same room.

Step 1: Sort meetings by start time

[1,4], [2,5], [7,9]

Why: Sorting helps us check meetings in order of when they start.

Step 2: Create a min-heap and add the end time of the first meeting (4)

Heap: [4]

Why: We track the earliest meeting end time to reuse rooms.

Step 3: Check second meeting start (2) against earliest end time in heap (4)

Heap: [4]

Why: 2 < 4 means overlap, so we need a new room.

Step 4: Add second meeting end time (5) to heap

Heap: [4, 5]

Why: Two meetings overlap, so two rooms are needed.

Step 5: Check third meeting start (7) against earliest end time in heap (4)

Heap before removal: [4, 5]

Why: 7 >= 4 means one room is free now.

Step 6: Remove 4 from heap and add 9

Heap after removal and addition: [5, 9]

Why: Reuse room that ended at 4 for meeting starting at 7.

Step 7: Final heap size is 2

Heap: [5, 9]

Why: Heap size shows minimum rooms needed.

Result:

Heap: [5, 9]
Minimum rooms required: 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        // Sort meetings by start time
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });
        
        // Min-heap to track earliest end time
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        // Add first meeting end time
        minHeap.push(intervals[0][1]);
        
        for (int i = 1; i < intervals.size(); i++) {
            // If current meeting starts after or when earliest meeting ends
            if (intervals[i][0] >= minHeap.top()) {
                minHeap.pop(); // Room freed
            }
            minHeap.push(intervals[i][1]); // Add current meeting end time
        }
        
        // Number of rooms needed is heap size
        return minHeap.size();
    }
};

int main() {
    Solution sol;
    vector<vector<int>> meetings = {{1,4}, {2,5}, {7,9}};
    cout << sol.minMeetingRooms(meetings) << "\n";
    return 0;
}

sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });

Sort meetings by start time to process in order.

minHeap.push(intervals[0][1]);

Add end time of first meeting to track room usage.

if (intervals[i][0] >= minHeap.top()) { minHeap.pop(); }

If current meeting starts after earliest end, free a room.

minHeap.push(intervals[i][1]);

Add current meeting end time to heap.

return minHeap.size();

Heap size equals minimum rooms needed.

Output

2

Complexity Analysis

Time: O(n log n) because we sort the meetings and then for each meeting we do heap operations which take O(log n)

Space: O(n) because in the worst case all meetings overlap and we store all end times in the heap

vs Alternative: A naive approach checks all pairs for overlap leading to O(n^2) time, this heap method is more efficient.

Edge Cases

empty meetings list

returns 0 rooms needed

DSA C++

if (intervals.empty()) return 0;

all meetings non-overlapping

returns 1 room needed

DSA C++

if (intervals[i][0] >= minHeap.top()) { minHeap.pop(); }

all meetings fully overlapping

returns number of meetings as rooms needed

DSA C++

minHeap.push(intervals[i][1]);

When to Use This Pattern

When you need to schedule intervals without overlap and find minimum resources, use a min-heap to track earliest finishing times and assign rooms efficiently.

Common Mistakes

Mistake: Not sorting meetings by start time before processing
Fix: Sort meetings by start time first to process in chronological order.

Mistake: Not removing ended meetings from the heap before adding new ones
Fix: Check if current meeting starts after earliest end time and pop from heap to reuse room.

Summary

Finds the minimum number of rooms needed so no meetings overlap in the same room.

Use when scheduling overlapping intervals and you want to minimize resources like rooms.

Sort meetings by start time and use a min-heap to track earliest end times to reuse rooms efficiently.

Practice

1. What does the "Meeting Rooms Problem Minimum Rooms Required" ask you to find given a list of meeting time intervals?

easy

A. The maximum length of a single meeting

B. The total number of meetings scheduled

C. The minimum number of rooms needed so no meetings overlap

D. The earliest meeting start time

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of rooms needed so that no two meetings overlap in the same room.

2. Step 2: Clarify what is being counted

   We count how many meetings happen at the same time to find the minimum rooms required.

3. Final Answer:

   The minimum number of rooms needed so no meetings overlap -> Option C

4. Quick Check:

   Minimum rooms = max overlapping meetings [OK]

Hint: Count max overlapping meetings to find minimum rooms [OK]

Common Mistakes:

• Confusing total meetings with rooms needed
• Thinking earliest start time is the answer
• Ignoring overlapping intervals

2. Which of the following C++ code snippets correctly sorts a vector of meeting intervals by their start time? Assume intervals is a vector of pairs where first is start and second is end time.

easy

A. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first > b.first; });

B. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first < b.first; });

C. std::sort(intervals.rbegin(), intervals.rend());

D. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.second < b.second; });

Solution

1. Step 1: Identify sorting by start time

   We want to sort intervals by their start time, which is stored in a.first.

2. Step 2: Check lambda comparator correctness

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first < b.first; }); uses a lambda comparing a.first < b.first, which sorts ascending by start time correctly.

3. Final Answer:

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first < b.first; }); -> Option B

4. Quick Check:

   Sort by start time ascending [OK]

Hint: Sort intervals by start time using lambda with a.first < b.first [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using default sort without comparator (may sort by first but not guaranteed)
• Sorting descending when ascending is needed

3. What is the output of the following C++ code snippet that calculates the minimum number of meeting rooms required?

std::vector> intervals = {{0,30}, {5,10}, {15,20}};
std::vector<int> starts, ends;
for(auto &i : intervals) {
    starts.push_back(i.first);
    ends.push_back(i.second);
}
std::sort(starts.begin(), starts.end());
std::sort(ends.begin(), ends.end());
int rooms = 0, end_ptr = 0;
for(int i = 0; i < starts.size(); i++) {
    if(starts[i] < ends[end_ptr]) rooms++;
    else end_ptr++;
}
std::cout << rooms << std::endl;

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort start and end times

   Starts = [0,5,15], Ends = [10,20,30]

2. Step 2: Iterate and count rooms

   i=0: 0<10 true rooms=1
   i=1: 5<10 true rooms=2
   i=2: 15<10 false end_ptr=1 rooms=2

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Compare starts and ends with two pointers to count rooms [OK]

Common Mistakes:

• Not sorting start and end arrays
• Incrementing rooms incorrectly
• Confusing when to move end pointer

4. The following code attempts to find the minimum number of meeting rooms needed but has a bug. What is the bug?

std::vector> intervals = {{1,5}, {2,6}, {8,10}};
std::sort(intervals.begin(), intervals.end());
int rooms = 1;
for(int i = 1; i < intervals.size(); i++) {
    if(intervals[i].first < intervals[i-1].second) rooms++;
}
std::cout << rooms << std::endl;

medium

A. The loop should start from i = 0, not i = 1

B. The intervals vector is not sorted correctly

C. The rooms variable should start at 0, not 1

D. It only compares each meeting with the previous one, missing overlaps with earlier meetings

Solution

1. Step 1: Analyze overlap check logic

   The code only checks if current meeting starts before previous meeting ends, ignoring overlaps with other meetings.

2. Step 2: Understand why this causes error

   This misses cases where a meeting overlaps with a meeting before the previous one, undercounting rooms needed.

3. Final Answer:

   It only compares each meeting with the previous one, missing overlaps with earlier meetings -> Option D

4. Quick Check:

   Check all overlaps, not just adjacent meetings [OK]

Hint: Check overlaps with all active meetings, not just previous [OK]

Common Mistakes:

• Assuming sorting fixes all overlap checks
• Starting loop at wrong index
• Incorrect initial rooms count

5. Given the following meeting intervals: {{0, 10}, {5, 15}, {10, 20}, {15, 25}, {20, 30}}, what is the minimum number of meeting rooms required to schedule all meetings without overlap?

hard

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Sort start and end times

   Starts = [0,5,10,15,20], Ends = [10,15,20,25,30]

2. Step 2: Use two pointers to count rooms

   i=0: 0<10 rooms=1
   i=1: 5<10 rooms=2
   i=2: 10<10 false end_ptr=1 rooms=2
   i=3: 15<15 false end_ptr=2 rooms=2
   i=4: 20<20 false end_ptr=3 rooms=2

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Track starts and ends with pointers to find max overlaps [OK]

Common Mistakes:

• Counting all meetings as overlapping
• Not moving end pointer correctly
• Misreading intervals causing wrong overlaps