Meeting Rooms Problem Minimum Rooms Required in DSA Rust

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 friends who want to use the same study room at different times. You want to know how many rooms you need so everyone can study without waiting.

Meetings:
[1,4] -> [2,5] -> [7,9] -> null
Rooms needed: ?

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 when rooms become free by their meeting end times.

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

Heap: [4]

Why: Since 2 < 4, the second meeting overlaps, 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 occupied.

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

Heap: [4, 5]

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

Step 6: Remove earliest end time (4) from heap and add third meeting end time (9)

Heap: [5, 9]

Why: Reuse the freed room for the third meeting.

Result:

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

Annotated Code

DSA Rust

use std::collections::BinaryHeap;
use std::cmp::Reverse;

#[derive(Debug)]
struct Meeting {
    start: i32,
    end: i32,
}

fn min_meeting_rooms(meetings: &mut Vec<Meeting>) -> usize {
    // Sort meetings by start time
    meetings.sort_by_key(|m| m.start);

    // Min-heap to track earliest end time
    let mut heap = BinaryHeap::new();

    for meeting in meetings {
        // If a room is free (earliest end <= current start), reuse it
        if let Some(&Reverse(earliest_end)) = heap.peek() {
            if earliest_end <= meeting.start {
                heap.pop(); // free the room
            }
        }
        // Add current meeting's end time
        heap.push(Reverse(meeting.end));
    }

    heap.len()
}

fn main() {
    let mut meetings = vec![
        Meeting { start: 1, end: 4 },
        Meeting { start: 2, end: 5 },
        Meeting { start: 7, end: 9 },
    ];

    let rooms = min_meeting_rooms(&mut meetings);
    println!("Minimum rooms needed: {}", rooms);
}

meetings.sort_by_key(|m| m.start);

Sort meetings by their start time to process in order.

if let Some(&Reverse(earliest_end)) = heap.peek() {

Check the earliest meeting end time currently in rooms.

if earliest_end <= meeting.start { heap.pop(); }

If a room is free before current meeting starts, remove it from heap to reuse.

heap.push(Reverse(meeting.end));

Add current meeting's end time to track room occupation.

heap.len()

Number of rooms needed equals the heap size after processing all meetings.

Output

Minimum rooms needed: 2

Complexity Analysis

Time: O(n log n) because we sort the meetings and use a heap for n meetings with log n operations each

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 O(n^2), this heap method is more efficient.

Edge Cases

No meetings

Returns 0 rooms needed

DSA Rust

meetings.sort_by_key(|m| m.start);

All meetings non-overlapping

Returns 1 room needed

DSA Rust

if earliest_end <= meeting.start { heap.pop(); }

All meetings fully overlapping

Returns number of meetings as rooms needed

DSA Rust

heap.push(Reverse(meeting.end));

When to Use This Pattern

When you see a problem asking for minimum resources to schedule overlapping intervals, use the min-heap approach to track earliest finishing times and reuse resources.

Common Mistakes

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

Mistake: Using max-heap instead of min-heap for end times
Fix: Use a min-heap to always get the earliest finishing meeting to free rooms.

Mistake: Not popping from heap when a room is free
Fix: Pop from heap when earliest end time is less or equal to current meeting start to reuse room.

Summary

Calculates the minimum number of rooms needed to hold all meetings without overlap.

Use when scheduling intervals where overlapping means needing separate resources.

Track earliest finishing meeting with a min-heap 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 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