Meeting Rooms Problem Minimum Rooms Required in DSA Rust - 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 <= interval start

↓

Pop min-heap

↓

Push current interval end

↓

Heap size = rooms needed

↓

Done

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

Execution Sample

DSA Rust

let intervals = vec![(0, 30), (5, 10), (15, 20)];
intervals.sort_by_key(|k| k.0);
let mut heap = std::collections::BinaryHeap::<std::cmp::Reverse<i32>>::new();
for interval in intervals {
  // logic to add/pop heap
}
heap.len()

Sort intervals by start time, then use a min-heap to track meeting end times to find minimum rooms.

Execution Table

Step	Operation	Current Interval	Min-Heap Top (Earliest End)	Heap Action	Heap State (End Times)	Rooms Needed
1	Sort intervals	[(0,30),(5,10),(15,20)]	-	Sorted	[]	0
2	Process interval	(0,30)	-	Push end=30	[30]	1
3	Process interval	(5,10)	30	Push end=10	[10,30]	2
4	Process interval	(15,20)	10	Pop 10, Push 20	[20,30]	2
5	End	-	-	Heap size = 2	[20,30]	2

💡 All intervals processed; heap size 2 means minimum 2 rooms needed.

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)]
heap (min-heap of ends)	[]	[30]	[10,30]	[20,30]	[20,30]
rooms_needed	0	1	2	2	2

Key Moments - 3 Insights

Why do we pop from the heap when the earliest end time is <= current interval start?

Because that means a meeting room got free before the current meeting starts, so we can reuse that room instead of adding a new one. See step 4 in execution_table where 10 is popped before pushing 20.

Why do we push the current interval's end time into the heap every time?

We always add the current meeting's end time to track when that room will be free. This helps us know if future meetings can reuse rooms. Refer to steps 2, 3, and 4 where ends 30, 10, and 20 are pushed.

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

Because each end time in the heap represents a meeting currently occupying a room. The heap size shows how many rooms are in use 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 heap state after processing interval (5,10)?

A [30, 10]

B [10]

C [30]

D [5, 10]

💡 Hint

Check the 'Heap State' column in execution_table row for step 3.

At which step does the algorithm reuse a room by popping from the heap?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Pop' action in the 'Heap Action' column in execution_table.

If the intervals were [(0,10), (10,20), (20,30)], what would be the minimum rooms needed?

A 1

B 2

C 3

D 0

💡 Hint

Intervals do not overlap; check how heap size changes when intervals start exactly when previous ends.

Concept Snapshot

Meeting Rooms Minimum Rooms Required:
- Sort intervals by start time
- Use min-heap to track earliest meeting end
- For each interval:
  - If earliest end <= current start, pop heap (reuse room)
  - 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 times. Then, use a min-heap to keep track of the end times of meetings currently occupying rooms. For each meeting, if the earliest ending meeting ends before or when the current meeting starts, pop it from the heap to reuse that room. Always push the current meeting's end time into the heap. The size of the heap after processing all meetings is the minimum number of rooms required.

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 number of meetings that can be scheduled in one room

B. The total duration of all meetings combined

C. The minimum number of rooms needed so that no meetings overlap in the same room

D. The earliest start time among all meetings

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 overlap at the same time to know how many rooms are needed.

3. Final Answer:

   The minimum number of rooms needed so that no meetings overlap in the same room -> Option C

4. Quick Check:

   Minimum rooms = max overlapping meetings [OK]

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

Common Mistakes:

• Confusing total meetings with rooms needed
• Thinking about meeting durations instead of overlaps
• Assuming rooms equal to total meetings

2. Which Rust data structure is best suited to efficiently track ongoing meetings when solving the Meeting Rooms problem?

easy

A. LinkedList of meeting intervals

B. HashMap with meeting durations as keys

C. Vec (vector) sorted by start times

D. Binary heap (priority queue) to track earliest ending meeting

Solution

1. Step 1: Identify the need to track earliest ending meeting

   We need to know which meeting ends earliest to free a room for the next meeting.

2. Step 2: Choose data structure for efficient retrieval

   A binary heap (priority queue) efficiently gives the earliest ending meeting in O(log n) time.

3. Final Answer:

   Binary heap (priority queue) to track earliest ending meeting -> Option D

4. Quick Check:

   Priority queue tracks earliest end time [OK]

Hint: Use a min-heap to track earliest meeting end times [OK]

Common Mistakes:

• Using HashMap which doesn't keep order
• Using LinkedList which is inefficient for min retrieval
• Using Vec without sorting or heap structure

3. Given the following Rust code snippet, what is the output?

let intervals = vec![(0, 30), (5, 10), (15, 20)];
// Function returns minimum rooms required
let result = min_meeting_rooms(intervals);
println!("{}", result);

fn min_meeting_rooms(mut intervals: Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.0);
    let mut heap = std::collections::BinaryHeap::new();
    for interval in intervals {
        if let Some(&Reverse(end)) = heap.peek() {
            if interval.0 >= end {
                heap.pop();
            }
        }
        heap.push(Reverse(interval.1));
    }
    heap.len() as i32
}

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: (0,30), (5,10), (15,20)

2. Step 2: Use min-heap to track end times and count rooms

   First meeting (0,30): push 30
   Second meeting (5,10): 5 < 30, push 10 (rooms=2)
   Third meeting (15,20): 15 >= 10, pop 10, push 20 (rooms=2)

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Sort by start, use min-heap for end times to count rooms [OK]

Common Mistakes:

• Not sorting intervals before processing
• Not popping from heap when room frees
• Counting total meetings instead of overlaps

4. The following Rust code for minimum meeting rooms has a bug. What is the bug?

fn min_meeting_rooms(mut intervals: Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.1);
    let mut heap = std::collections::BinaryHeap::new();
    for interval in intervals {
        if let Some(&Reverse(end)) = heap.peek() {
            if interval.0 >= end {
                heap.pop();
            }
        }
        heap.push(Reverse(interval.1));
    }
    heap.len() as i32
}

medium

A. Sorting intervals by end time instead of start time causes incorrect room count

B. Using BinaryHeap instead of Vec causes runtime error

C. Not pushing start times into the heap causes logic failure

D. Missing return statement at the end

Solution

1. Step 1: Check sorting criteria

   The code sorts intervals by end time, but we must sort by start time to process meetings in order.

2. Step 2: Understand impact on heap logic

   Sorting by end time breaks the logic of comparing current start with earliest end, leading to wrong room count.

3. Final Answer:

   Sorting intervals by end time instead of start time causes incorrect room count -> Option A

4. Quick Check:

   Sort by start time, not end time [OK]

Hint: Always sort intervals by start time before processing [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Confusing heap usage with wrong keys
• Ignoring heap pop condition

5. You have meetings: [(1,4), (2,5), (7,9), (3,6), (10,11)]. Using the minimum rooms required approach, what is the minimum number of rooms needed?

hard

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Sort intervals by start time

   Sorted: (1,4), (2,5), (3,6), (7,9), (10,11)

2. Step 2: Track overlapping meetings with min-heap

   Push end 4 (room 1)
   Next start 2 < 4, push 5 (room 2)
   Next start 3 < 4, push 6 (room 3)
   Next start 7 >= 4, pop 4, pop 5, pop 6, push 9 (room 1)
   Next start 10 >= 9, pop 9, push 11 (room 1)
   Max rooms used simultaneously = 3

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Max overlaps at once = 3 rooms [OK]

Hint: Count max overlaps after sorting by start time [OK]

Common Mistakes:

• Not sorting intervals before processing
• Counting total meetings instead of overlaps
• Not popping freed rooms from heap