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 if earliest end time <= current start

↓

Pop from heap

↓

Push current end time

↓

Repeat for all intervals

↓

Heap size = minimum rooms needed

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

Execution Sample

DSA C#

int MinMeetingRooms(int[][] intervals) {
  Array.Sort(intervals, (a,b) => a[0] - b[0]);
  var heap = new SortedSet<int>();
  foreach(var interval in intervals) {
    while(heap.Count > 0 && heap.Min <= interval[0]) {
      heap.Remove(heap.Min);
    }
    heap.Add(interval[1]);
  }
  return heap.Count;
}

Sort intervals, use a min-heap to track earliest finishing meeting, count rooms needed.

Execution Table

Step	Operation	Current Interval	Heap Before	Heap After	Rooms Needed
1	Sort intervals	[0, 30]	[]	[]	0
2	Process interval	[0, 30]	[]	[30]	1
3	Process interval	[5, 10]	[30]	[10, 30]	2
4	Process interval	[15, 20]	[10, 30]	[20, 30]	2
5	End	-	[20, 30]	[20, 30]	2

💡 All intervals processed; heap size 2 means 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	[]	[30]	[10,30]	[20,30]	[20,30]
rooms_needed	0	1	2	2	2

Key Moments - 3 Insights

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

Because that meeting room is now free and can be reused, so we remove the old end time before adding the new one. See step 4 in execution_table where 10 is replaced by 20.

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

Each end time in the heap represents a meeting occupying a room. The heap size shows how many meetings overlap at once. At the end, heap size is 2 meaning 2 rooms needed (step 5).

Why do we sort intervals by start time first?

Sorting ensures we process meetings in order of start time, so we can assign rooms correctly as meetings come. Without sorting, we can't track overlaps properly.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the heap after processing interval [5, 10]?

A [30]

B [10, 30]

C [5, 10]

D [20, 30]

💡 Hint

Check the 'Heap After' column for step 3 in execution_table.

At which step does the heap size first become 2?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

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

If the interval [15, 20] started at 30 instead of 15, how would the heap size after step 4 change?

A It would remain 2

B It would become 3

C It would become 1

D It would become 0

💡 Hint

Think about whether the meeting starting at 30 overlaps with others in the heap after step 4.

Concept Snapshot

Meeting Rooms Minimum Rooms Needed:
- Sort intervals by start time
- Use min-heap to track earliest end times
- For each interval:
  - If earliest end <= current start, reuse room (pop heap)
  - Add current end to heap
- Heap size at end = minimum rooms required

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, check if the earliest finishing meeting ends before or when the current meeting starts. If yes, remove that end time from the heap, meaning the room is free to reuse. Add the current meeting's end time to the heap. The size of the heap after processing all meetings tells us the minimum number of rooms required. This approach efficiently manages overlapping meetings and room allocation.

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 duration of a single meeting

B. The earliest start time among all meetings

C. The total number of meetings scheduled

D. The minimum number of meeting rooms needed to hold all meetings without overlap

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 rooms, not meetings or durations. The goal is to avoid time conflicts in the same room.

3. Final Answer:

   The minimum number of meeting rooms needed to hold all meetings without overlap -> Option D

4. Quick Check:

   Minimum rooms = no overlapping meetings at the same time [OK]

Hint: Count overlaps to find minimum rooms needed [OK]

Common Mistakes:

• Confusing number of meetings with number of rooms
• Thinking about meeting durations instead of overlaps
• Ignoring overlapping intervals

2. Which of the following C# code snippets correctly initializes a list of meeting intervals represented as tuples of start and end times?

easy

A. var meetings = new List<(int, int)> { 9, 10, 11, 12 };

B. var meetings = new List { [9, 10], [11, 12] };

C. var meetings = new List<(int start, int end)> { (9, 10), (11, 12) };

D. var meetings = new List<(int start, int end)> { (start: 9, end: 10), (start: 11) };

Solution

1. Step 1: Check tuple list initialization syntax

   var meetings = new List<(int start, int end)> { (9, 10), (11, 12) }; correctly uses List of tuples with named elements and proper tuple syntax.

2. Step 2: Identify errors in other options

   var meetings = new List { [9, 10], [11, 12] }; uses invalid array syntax inside list initialization. var meetings = new List<(int, int)> { 9, 10, 11, 12 }; tries to add ints directly, not tuples. var meetings = new List<(int start, int end)> { (start: 9, end: 10), (start: 11) }; misses end value in second tuple.

3. Final Answer:

   var meetings = new List<(int start, int end)> { (9, 10), (11, 12) }; -> Option C

4. Quick Check:

   Correct tuple list syntax = var meetings = new List<(int start, int end)> { (9, 10), (11, 12) }; [OK]

Hint: Use (int, int) tuples with curly braces for intervals [OK]

Common Mistakes:

• Using square brackets instead of parentheses for tuples
• Missing tuple elements or names
• Adding ints instead of tuples

3. Given the following C# code, what is the output?

var intervals = new List<(int start, int end)>{ (0, 30), (5, 10), (15, 20) };
int minRooms = MinMeetingRooms(intervals);
Console.WriteLine(minRooms);

int MinMeetingRooms(List<(int start, int end)> intervals) {
    var starts = intervals.Select(i => i.start).OrderBy(t => t).ToList();
    var ends = intervals.Select(i => i.end).OrderBy(t => t).ToList();
    int rooms = 0, endIndex = 0;
    foreach (var start in starts) {
        if (start < ends[endIndex]) rooms++;
        else endIndex++;
    }
    return rooms;
}

medium

A. 3

B. 2

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 starts comparing with ends

   start=0 < 10 -> rooms=1; start=5 < 10 -> rooms=2; start=15 >= 10 -> endIndex=1, no increment rooms; final rooms=2

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Overlapping intervals = 2 rooms needed [OK]

Hint: Sort starts and ends, count overlaps with end pointer [OK]

Common Mistakes:

• Not sorting start and end times separately
• Incrementing rooms incorrectly when meetings don't overlap
• Confusing start and end comparisons

4. The following code attempts to find the minimum number of meeting rooms needed. What is the bug?

int MinRooms(List<(int start, int end)> intervals) {
    intervals.Sort((a, b) => a.start.CompareTo(b.start));
    var heap = new SortedSet<int>();
    foreach (var interval in intervals) {
        if (heap.Count > 0 && interval.start >= heap.Min) {
            heap.Remove(heap.Min);
        }
        heap.Add(interval.end);
    }
    return heap.Count;
}

medium

A. SortedSet does not allow duplicate end times, causing incorrect room count

B. Intervals are not sorted by end time before processing

C. The condition should be interval.start > heap.Min instead of >= to avoid overlap

D. Heap should store start times instead of end times

Solution

1. Step 1: Understand SortedSet behavior

   SortedSet does not allow duplicates, so multiple meetings ending at same time cause missing removals.

2. Step 2: Identify impact on room count

   Without duplicates, heap may keep extra end times, inflating room count incorrectly.

3. Final Answer:

   SortedSet does not allow duplicate end times, causing incorrect room count -> Option A

4. Quick Check:

   Data structure must allow duplicates for correct room count [OK]

Hint: Use a min-heap that supports duplicates, not SortedSet [OK]

Common Mistakes:

• Using SortedSet instead of a priority queue or min-heap
• Confusing start and end time comparisons
• Incorrect condition for removing from heap

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

hard

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Sort start and end times

   Starts = [1, 2, 3, 7, 10], Ends = [4, 5, 6, 9, 11]

2. Step 2: Count overlaps using two pointers

   start=1 < 4 rooms=1; start=2 < 4 rooms=2; start=3 < 4 rooms=3; start=7 >= 4 endIndex=1 no increment rooms; start=10 >= 5 endIndex=2 no increment rooms; final rooms=3

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Maximum overlaps = 3 rooms needed [OK]

Hint: Sort starts and ends, increment rooms on overlap [OK]

Common Mistakes:

• Not sorting intervals before processing
• Counting rooms incorrectly when meetings end
• Ignoring overlapping intervals