Meeting Rooms Problem Minimum Rooms Required in DSA C#

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 a single phone booth at different times. You want to know how many booths you need so that no one waits.

Meetings: [1,4], [2,5], [7,9]
Timeline: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
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 for end times and add first meeting end time 4

Heap: [4]

Why: We track earliest finishing meeting to reuse rooms.

Step 3: Check second meeting start 2 against earliest end 4; 2 < 4 means overlap, add end 5 to heap

Heap: [4, 5]

Why: Overlap means need a new room.

Step 4: Check third meeting start 7 against earliest end 4; 7 >= 4 means room freed, remove 4 from heap

Heap: [5]

Why: Room freed, so we can reuse it.

Step 5: Add third meeting end 9 to heap

Heap: [5, 9]

Why: Track current meetings' end times.

Result:

Heap size is 2, so minimum rooms needed = 2

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class MeetingRooms {
    public static int MinMeetingRooms(int[][] intervals) {
        if (intervals.Length == 0) return 0;

        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        var minHeap = new SortedSet<(int end, int id)>(Comparer<(int, int)>.Create((a, b) => a.end != b.end ? a.end - b.end : a.id - b.id));
        int idCounter = 0;

        minHeap.Add((intervals[0][1], idCounter++));

        for (int i = 1; i < intervals.Length; i++) {
            var currentStart = intervals[i][0];
            var earliestEnd = minHeap.First().end;

            if (currentStart >= earliestEnd) {
                var toRemove = minHeap.First();
                minHeap.Remove(toRemove);
            }

            minHeap.Add((intervals[i][1], idCounter++));
        }

        return minHeap.Count;
    }

    public static void Main() {
        int[][] meetings = new int[][] {
            new int[] {1,4},
            new int[] {2,5},
            new int[] {7,9}
        };

        int rooms = MinMeetingRooms(meetings);
        Console.WriteLine(rooms);
    }
}

Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

Sort meetings by start time to process in order

minHeap.Add((intervals[0][1], idCounter++));

Add first meeting end time to track earliest finishing meeting

var earliestEnd = minHeap.First().end;

Get earliest meeting end time to check room availability

if (currentStart >= earliestEnd) { minHeap.Remove(minHeap.First()); }

If current meeting starts after earliest ends, free that room

minHeap.Add((intervals[i][1], idCounter++));

Add current meeting end time to track ongoing meetings

return minHeap.Count;

Number of rooms needed equals number of ongoing meetings tracked

Output

2

Complexity Analysis

Time: O(n log n) because we sort the meetings and use a heap to track end times for n meetings

Space: O(n) because in worst case all meetings overlap and we store all end times in the heap

vs Alternative: Naive approach checks all pairs for overlap O(n^2), this heap method is more efficient

Edge Cases

empty meetings list

returns 0 rooms needed

DSA C#

if (intervals.Length == 0) return 0;

all meetings non-overlapping

returns 1 room needed

DSA C#

if (currentStart >= earliestEnd) { minHeap.Remove(minHeap.First()); }

all meetings fully overlapping

returns number of meetings as rooms needed

DSA C#

minHeap.Add((intervals[i][1], idCounter++));

When to Use This Pattern

When you see a problem asking for minimum rooms or resources to schedule overlapping intervals, use a min-heap to track earliest finishing times and allocate rooms efficiently.

Common Mistakes

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

Mistake: Using a max-heap or wrong data structure for tracking end times
Fix: Use a min-heap or sorted set to always get earliest finishing meeting

Mistake: Not removing finished meetings from the heap before adding new ones
Fix: Remove earliest end time if current meeting starts after it to reuse room

Summary

Finds the minimum number of rooms needed so no meetings overlap in the same room.

Use when scheduling overlapping intervals and you want to minimize resource usage.

Sort meetings by start time and track earliest finishing meetings 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 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