Meeting Rooms Problem Minimum Rooms Required in DSA Python - Time & Space Complexity

Time Complexity: Meeting Rooms Problem Minimum Rooms Required

O(n log n)

Understanding Time Complexity

We want to find out how the time needed to find the minimum number of meeting rooms changes as the number of meetings grows.

Specifically, how does the code handle more meetings efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from heapq import heappush, heappop

def minMeetingRooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for interval in intervals:
        if heap and heap[0] <= interval[0]:
            heappop(heap)
        heappush(heap, interval[1])
    return len(heap)
    

This code finds the minimum number of meeting rooms needed by sorting meetings and using a heap to track end times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all meetings once.
• How many times: Once for each meeting (n times).
• Inside loop: Heap operations (push and sometimes pop) happen for each meeting.

How Execution Grows With Input

As the number of meetings increases, the sorting and heap operations grow too.

Input Size (n)	Approx. Operations
10	About 10 log 10 + 10 operations
100	About 100 log 100 + 100 operations
1000	About 1000 log 1000 + 1000 operations

Pattern observation: The time grows a bit faster than just the number of meetings because of sorting and heap operations, but not as fast as checking every pair.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a little more than linearly as meetings increase, mainly due to sorting and managing the heap.

Common Mistake

[X] Wrong: "The code just loops through meetings once, so it must be O(n)."

[OK] Correct: Sorting the meetings first and using a heap for end times adds extra work that grows with n log n, not just n.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why using sorting plus a heap is efficient for scheduling problems.

Self-Check

"What if we used a simple list instead of a heap to track end times? How would the time complexity change?"