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.