Meeting Rooms Problem Minimum Rooms Required in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Minimum Meeting Rooms Required - Output Check

What is the output of the following Rust code that calculates the minimum number of meeting rooms required for given intervals?

DSA Rust

fn min_meeting_rooms(intervals: Vec<(i32, i32)>) -> i32 {
    let mut starts: Vec<i32> = intervals.iter().map(|x| x.0).collect();
    let mut ends: Vec<i32> = intervals.iter().map(|x| x.1).collect();
    starts.sort_unstable();
    ends.sort_unstable();
    let mut rooms = 0;
    let mut end_ptr = 0;
    for start in starts {
        if start < ends[end_ptr] {
            rooms += 1;
        } else {
            end_ptr += 1;
        }
    }
    rooms
}

fn main() {
    let intervals = vec![(0, 30), (5, 10), (15, 20)];
    println!("{}", min_meeting_rooms(intervals));
}

A 3

B 2

C 1

D 0

💡 Hint

Think about how many meetings overlap at the same time.

The code sorts start and end times separately and uses two pointers to track overlaps. It increments rooms when a meeting starts before the earliest ending meeting ends. For the given intervals, the maximum overlap is 2.

🧠 Conceptual

intermediate

Understanding the Two Pointer Technique in Meeting Rooms

In the Meeting Rooms problem, why do we sort the start and end times separately and use two pointers to traverse them?

A To count the total number of meetings without overlaps.

B To merge intervals into one big interval.

C To efficiently track when meetings start and end to find overlaps without checking every pair.

D To sort meetings by their duration.

💡 Hint

Think about how sorting helps in comparing start and end times in order.

Sorting start and end times separately allows us to compare the earliest starting meeting with the earliest ending meeting to detect overlaps efficiently.

🔧 Debug

advanced

Identify the Bug in Meeting Rooms Code

What error will the following Rust code produce when run, and why?

DSA Rust

fn min_meeting_rooms(intervals: Vec<(i32, i32)>) -> i32 {
    let mut starts: Vec<i32> = intervals.iter().map(|x| x.0).collect();
    let mut ends: Vec<i32> = intervals.iter().map(|x| x.1).collect();
    starts.sort();
    ends.sort();
    let mut rooms = 0;
    let mut end_ptr = 0;
    for start in starts {
        if start <= ends[end_ptr] {
            rooms += 1;
        } else {
            end_ptr += 1;
        }
    }
    rooms
}

fn main() {
    let intervals = vec![(0, 30), (5, 10), (10, 20)];
    println!("{}", min_meeting_rooms(intervals));
}

A Incorrect output: returns 3 instead of 2

B Index out of bounds panic at ends[end_ptr] when end_ptr exceeds ends length

C Compilation error due to missing semicolon

D No error, outputs 2 correctly

💡 Hint

Check the comparison operator in the if condition and how end_ptr is incremented.

Using <= causes rooms to increment even when a meeting starts exactly when another ends, leading to overcounting rooms. The output is 3 instead of the correct 2.

📝 Syntax

advanced

Identify the Syntax Error in Rust Meeting Rooms Code

Which option contains a syntax error in this Rust code snippet for minimum meeting rooms?

DSA Rust

fn min_meeting_rooms(intervals: Vec<(i32, i32)>) -> i32 {
    let mut starts = intervals.iter().map(|x| x.0).collect::<Vec<i32>>();
    let mut ends = intervals.iter().map(|x| x.1).collect::<Vec<i32>>();
    starts.sort_unstable();
    ends.sort_unstable();
    let mut rooms = 0;
    let mut end_ptr = 0;
    for start in starts {
        if start < ends[end_ptr] {
            rooms += 1;
        } else {
            end_ptr += 1;
        }
    }
    rooms
}

A Incorrect variable declaration for rooms

B Missing curly braces around if-else blocks

C Incorrect function return type

D Missing semicolon after starts.sort_unstable()

💡 Hint

Look carefully at each line's ending punctuation.

The line 'starts.sort_unstable()' is missing a semicolon, causing a syntax error.

🚀 Application

expert

Calculate Minimum Meeting Rooms for Complex Intervals

Given the intervals [(1,4), (2,5), (7,9), (3,6), (10,11), (8,10)], what is the minimum number of meeting rooms required?

A 3

B 4

C 2

D 5

💡 Hint

Visualize overlapping intervals on a timeline and count maximum overlaps.

The maximum number of overlapping meetings is 3, occurring between intervals (1,4), (2,5), and (3,6).

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