Meeting Rooms Problem Minimum Rooms Required in DSA C++ - Execution Trace

Concept Flow - Meeting Rooms Problem Minimum Rooms Required

Sort intervals by start time

↓

Initialize min-heap for end times

↓

For each interval

↓

Check min-heap top end time <= current start?

↓

Pop from heap

↓

Heap size = rooms needed

↓

Done

Sort meetings by start time, use a min-heap to track earliest ending meeting, allocate rooms by comparing current start with earliest end.

Execution Sample

DSA C++

intervals = [[0,30],[5,10],[15,20]];
sort intervals by start;
minHeap = empty;
for interval in intervals:
  if minHeap.top() <= interval.start:
    minHeap.pop();
  minHeap.push(interval.end);
return minHeap.size();

This code finds the minimum number of meeting rooms needed by sorting intervals and using a min-heap to track room availability.

Execution Table

Step	Operation	Current Interval	Min-Heap (End Times)	Heap Size (Rooms Needed)	Visual State
1	Sort intervals by start time	[0,30]	[]	0	[]
2	Process interval	[0,30]	[]	0	[]
3	Push end time 30	[0,30]	[30]	1	[0,30] -> Room 1 occupied until 30
4	Process interval	[5,10]	[30]	1	[0,30]
5	5 < 30, cannot reuse room, push 10	[5,10]	[10,30]	2	[0,30], [5,10] rooms occupied
6	Process interval	[15,20]	[10,30]	2	[0,30], [5,10]
7	15 >= 10, pop 10	[15,20]	[30]	1	[0,30] room occupied, freed room from 5,10
8	Push 20	[15,20]	[20,30]	2	[0,30], [15,20] rooms occupied
9	All intervals processed	-	[20,30]	2	Minimum rooms needed = 2

💡 All intervals processed, min-heap size 2 means 2 rooms needed

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 8	Final
interval	N/A	[0,30]	[5,10]	[15,20]	[15,20]	N/A
minHeap	[]	[30]	[10,30]	[30]	[20,30]	[20,30]
heap size	0	1	2	1	2	2

Key Moments - 3 Insights

Why do we pop from the min-heap when current interval start >= min-heap top?

Because the earliest meeting ended before current starts, so that room is free and can be reused. See execution_table rows 7 and 8 where 10 is popped before pushing 20.

Why do we push the current interval's end time even after popping?

We always push the current meeting's end time to track when this room will be free next. Popping frees a room, pushing reserves it again. See rows 7 and 8.

Why does the heap size represent the number of rooms needed?

Because each end time in the heap represents a meeting room currently occupied. The heap size shows how many rooms are in use simultaneously. See final heap size 2 in row 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the min-heap content?

A [10,30]

B [30]

C [5,10]

D []

💡 Hint

Check the 'Min-Heap (End Times)' column at step 5 in execution_table

At which step does the condition to pop from the heap become true for the first time?

A Step 4

B Step 7

C Step 6

D Step 8

💡 Hint

Look for the first step where popping from heap happens in execution_table

If the interval [5,10] was changed to [35,40], how would the heap size after step 5 change?

A It would become 3

B It would become 2

C It would remain 1

D It would become 0

💡 Hint

Consider that 35 > 30, so the room can be reused, reducing heap size growth

Concept Snapshot

Meeting Rooms Minimum Rooms Required:
- Sort intervals by start time
- Use min-heap to track earliest end time
- For each interval:
  - If earliest end <= current start, pop heap
  - Push current end
- Heap size = minimum rooms needed

Full Transcript

To find the minimum number of meeting rooms needed, first sort all meeting intervals by their start time. Then, use a min-heap to keep track of the end times of meetings currently occupying rooms. For each meeting, check if the earliest finishing meeting ends before the current meeting starts. If yes, pop that end time from the heap, meaning the room is free and can be reused. Then push the current meeting's end time into the heap. The size of the heap at the end tells how many rooms are needed simultaneously. This approach efficiently manages room allocation by always reusing rooms that free up earliest.

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