Meeting Rooms Problem Minimum Rooms Required in DSA Python

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 to make calls. Each call has a start and end time. You want to know how many phone booths you need so that no two friends have to wait.

Meetings: [1,4], [2,5], [7,9]
Timeline: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Rooms needed: 2 because [1,4] and [2,5] overlap

[1,4] -> Room 1
   ↑
[2,5] -> Room 2

[7,9] -> Room 1 (free again)

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 the earliest meeting end time to know when a room frees up.

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

Heap: [4]

Why: 2 < 4 means meetings overlap, 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 before removal: [4, 5]

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

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

Heap after removal and addition: [5, 9]

Why: Reuse the freed room for the third meeting.

Result:

Heap size is 2, so minimum rooms required = 2

Annotated Code

DSA Python

import heapq

class Solution:
    def minMeetingRooms(self, intervals):
        if not intervals:
            return 0

        # Sort meetings by start time
        intervals.sort(key=lambda x: x[0])

        # Use a min heap to track end times of meetings currently using rooms
        heap = []

        # Add the end time of the first meeting
        heapq.heappush(heap, intervals[0][1])

        for i in range(1, len(intervals)):
            # If the current meeting starts after or when the earliest meeting ends
            if intervals[i][0] >= heap[0]:
                # Remove the earliest ended meeting
                heapq.heappop(heap)

            # Add the current meeting's end time
            heapq.heappush(heap, intervals[i][1])

        # The heap size is the number of rooms needed
        return len(heap)

# Driver code
intervals = [[1,4], [2,5], [7,9]]
sol = Solution()
print(sol.minMeetingRooms(intervals))

intervals.sort(key=lambda x: x[0])

Sort meetings by their start time to process in order

heapq.heappush(heap, intervals[0][1])

Add end time of first meeting to heap to track room usage

if intervals[i][0] >= heap[0]:

Check if current meeting can reuse a freed room

heapq.heappop(heap)

Remove the meeting that ended earliest to free a room

heapq.heappush(heap, intervals[i][1])

Add current meeting's end time to heap to occupy a room

return len(heap)

Number of rooms needed equals the heap size

Output

2

Complexity Analysis

Time: O(n log n) because we sort the meetings and use a heap for insertions/removals

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

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

Edge Cases

empty list of meetings

returns 0 because no rooms are needed

DSA Python

if not intervals:
            return 0

all meetings non-overlapping

returns 1 because one room can hold all meetings

DSA Python

if intervals[i][0] >= heap[0]:

all meetings fully overlapping

returns number of meetings because each needs a separate room

DSA Python

heapq.heappush(heap, intervals[i][1])

When to Use This Pattern

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

Common Mistakes

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

Mistake: Not removing ended meetings from the heap before adding new ones
Fix: Check if current meeting can reuse a room by comparing start time with earliest end time and pop from heap if possible

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 use a min-heap to track earliest finishing meeting to reuse rooms.

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 minimum number of meeting rooms needed to hold all meetings without overlap

B. The maximum duration of a single meeting

C. The total number of meetings scheduled

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. Final Answer:

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

3. Quick Check:

   Minimum rooms = rooms needed to avoid overlap [OK]

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

Common Mistakes:

• Confusing total meetings with rooms needed
• Ignoring overlapping intervals
• Counting meeting duration instead of rooms

2. Which of the following Python code snippets correctly sorts a list of meeting intervals by their start time?

easy

A. intervals.sort(key=lambda x: x[1])

B. intervals.sort(key=lambda x: x[0])

C. intervals.sort()

D. intervals.sort(key=lambda x: x)

Solution

1. Step 1: Identify sorting by start time

   Each interval is a list or tuple like [start, end]. Sorting by x[0] sorts by start time.

2. Step 2: Check other options

   Sorting by x[1] sorts by end time, sort() without key sorts lexicographically (primarily by start but also end), lambda x: x sorts by whole interval.

3. Final Answer:

   intervals.sort(key=lambda x: x[0]) -> Option B

4. Quick Check:

   Sort by start time = key=lambda x: x[0] [OK]

Hint: Sort intervals by start time using key=lambda x: x[0] [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using sort() without key on lists of lists
• Confusing lambda syntax

3. What is the output of the following Python code that calculates minimum meeting rooms needed?

intervals = [[0, 30], [5, 10], [15, 20]]
starts = sorted([i[0] for i in intervals])
ends = sorted([i[1] for i in intervals])
rooms = 0
end_ptr = 0
for start in starts:
    if start < ends[end_ptr]:
        rooms += 1
    else:
        end_ptr += 1
print(rooms)

medium

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort start and end times

   starts = [0,5,15], ends = [10,20,30]. Initialize rooms=0, end_ptr=0.

2. Step 2: Trace the loop

   - start=0 < ends[0]=10: yes, rooms=1 (end_ptr=0)
   - start=5 < ends[0]=10: yes, rooms=2 (end_ptr=0)
   - start=15 < ends[0]=10: no, end_ptr=1
   Final rooms=2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Maximum concurrent meetings = 2 [OK]

Hint: Compare starts with earliest end to count rooms [OK]

Common Mistakes:

• Not moving end pointer correctly
• Counting rooms too many times
• Mixing start and end comparisons

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

def minMeetingRooms(intervals):
    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])
    rooms = 0
    end_ptr = 0
    for start in starts:
        if start > ends[end_ptr]:
            end_ptr += 1
        else:
            rooms += 1
    return rooms

print(minMeetingRooms([[0, 30], [5, 10], [15, 20]]))

medium

A. The comparison should be start < ends[end_ptr], not start > ends[end_ptr]

B. The ends list is not sorted

C. The rooms variable is not initialized

D. The function does not return any value

Solution

1. Step 1: Analyze the comparison logic

   The code uses if start > ends[end_ptr] to advance end_ptr, but correct logic requires advancing when start >= ends[end_ptr] (or equivalently, increment rooms when start < ends[end_ptr]).

2. Step 2: Understand impact

   Wrong comparison fails when start == ends[end_ptr], incorrectly counting extra room.

3. Final Answer:

   The comparison should be start < ends[end_ptr], not start > ends[end_ptr] -> Option A

4. Quick Check:

   Correct comparison fixes room count [OK]

Hint: Use start < ends[end_ptr] to check overlap [OK]

Common Mistakes:

• Using wrong comparison operator
• Not sorting ends list
• Forgetting to increment end pointer

5. Given the meeting intervals [[1, 4], [2, 5], [7, 9], [3, 6], [10, 11]], what is the minimum number of meeting rooms required to schedule all meetings without overlap?

hard

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Sort start and end times

   starts = [1,2,3,7,10], ends = [4,5,6,9,11].

2. Step 2: Simulate two-pointer algorithm

   rooms=0, end_ptr=0
   - start=1 < 4: rooms=1
   - start=2 < 4: rooms=2
   - start=3 < 4: rooms=3
   - start=7 < 4: no, end_ptr=1
   - start=10 < 5: no, end_ptr=2
   The final rooms value (3) is the max concurrent meetings needed.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlap (e.g., [1,4],[2,5],[3,6]) = 3 [OK]

Hint: Track overlaps by comparing starts and ends [OK]

Common Mistakes:

• Not updating end pointer correctly
• Counting all meetings as overlapping
• Ignoring meeting end times