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

↓

If min-heap top <= current start

↓

Pop min-heap top

↓

Push current end time

↓

Heap size = rooms needed

↓

Done

Sort meetings by start time, use a min-heap to track earliest ending meeting, reuse room if possible, else add new room.

Execution Sample

DSA C

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

Calculate minimum meeting rooms by sorting intervals and using a min-heap to track ongoing meetings.

Execution Table

Step	Operation	Current Interval	Min-Heap Before	Action	Min-Heap After	Rooms Needed	Visual State
1	Sort intervals	[[0,30],[5,10],[15,20]]	[]	Sort by start time	[[0,30],[5,10],[15,20]]	0	[0,30] [5,10] [15,20]
2	Process interval	[0,30]	[]	Push end=30	[30]	1	[30]
3	Process interval	[5,10]	[30]	5 < 30, push end=10	[10,30]	2	[10,30]
4	Process interval	[15,20]	[10,30]	10 <= 15, pop 10, push 20	[20,30]	2	[20,30]
5	End	No more intervals	[20,30]	Heap size=2	[20,30]	2	Minimum rooms = 2

💡 All intervals processed, min-heap size is the minimum rooms required.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
intervals	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]
minHeap	[]	[30]	[10,30]	[20,30]	[20,30]
rooms	0	1	2	2	2

Key Moments - 3 Insights

Why do we pop from the min-heap when the earliest end time is less than or equal to the current start time?

Because the meeting with the earliest end time has finished before the current meeting starts, so we can reuse that room. This is shown in step 4 where 10 <= 15, so we pop 10 and reuse the room.

Why do we push the current meeting's end time into the min-heap even after popping?

We push the current meeting's end time to track when this meeting will finish. This keeps the min-heap updated with ongoing meetings. Step 4 shows popping 10 and pushing 20.

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

Each element in the min-heap represents a meeting currently occupying a room. The heap size shows how many rooms are occupied simultaneously. At the end (step 5), heap size is 2, so 2 rooms are needed.

Visual Quiz - 3 Questions

Look at the execution table at step 3. What is the min-heap state before processing the interval [5,10]?

A []

B [10]

C [30]

D [20,30]

💡 Hint

Check the 'Min-Heap Before' column at step 3 in the execution table.

At which step does the min-heap size increase to 2?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Rooms Needed' column in the execution table to see when it changes to 2.

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

A It would remain 1

B It would increase to 2

C It would decrease to 0

D It would become 3

💡 Hint

If the new interval starts after the earliest end time, the room can be reused, so heap size does not increase.

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 the meeting intervals by their start times. Then, use a min-heap to keep track of the end times of meetings currently occupying rooms. For each meeting, if the earliest finishing meeting ends before or when the current meeting starts, reuse that room by popping from the heap. Always push the current meeting's end time into the heap. The size of the heap after processing all intervals is the minimum number of rooms required.