253. Meeting Rooms II
Model: qwen3.5:9b
Topics: Heap,Greedy,Sort
FAANG asked: 1
Acceptance rate: 47.1%
Problem Breakdown
We are given a list of meeting intervals, where each interval represents [start_time, end_time]. The goal is to determine the minimum number of conference rooms required so that no two meetings overlap in the same room.
Inputs: An array intervals containing pairs of integers representing start and end times.
Outputs: A single integer representing the count of concurrent overlapping intervals at their peak density.
Implicit Constraints & Edge Cases:
- Overlap Definition: If one meeting ends exactly when another starts (e.g.,
[0, 10]and[10, 20]), they can share a room because there is no overlap in time usage. The condition for reuse should beroom_end_time <= current_start_time. - Sorting: Since the input isn’t guaranteed to be sorted by start times, we must sort them first to process meetings chronologically based on demand.
- Data Range: Times go up to , so a direct array simulation (bucket approach) is not feasible due to memory constraints ( space). We need an algorithm dependent on the number of intervals, not time values.
Intuition
A brute-force solution would check every pair of meetings for overlap or simulate minute-by-minute occupancy across the entire timeline range. Both are inefficient: checking pairs is and simulation depends on coordinate magnitude (), which violates space constraints given large ranges but small interval counts.
The core insight here is Greedy Strategy with Resource Management. We want to reuse rooms whenever possible. To know when a room becomes available, we need the earliest ending meeting among all currently active meetings.
A Min-Heap (Priority Queue) is perfect for this because it allows us to efficiently retrieve and remove the smallest end time ( access after insertion). By sorting intervals by start times first, we ensure that when we consider a new meeting, we know exactly which rooms are currently occupied. If the earliest finishing room frees up before or at the current meeting’s start, we reuse it; otherwise, we allocate a new one.
Approach
- Sort: Sort
intervalsby their start times in ascending order. This ensures we process meetings as they arrive chronologically. - Initialize Heap: Create an empty min-heap to store the end times of active rooms. The size of this heap will represent the number of currently occupied rooms (and thus, at any point, the maximum concurrent usage).
- Iterate & Manage Rooms: Loop through each sorted interval:
- Check if the earliest finishing room (
heap[0]) has finished by or before the current meeting starts (interval.start). - If
heap[0] <= start: We can reuse that specific room. Pop it from the heap and push the new end time (updating when this reused room becomes free again). - If
heap[0] > startOR heap is empty: The current meeting cannot fit in any currently available room. Push its end time to the heap, effectively allocating a new room.
- Check if the earliest finishing room (
- Result: After processing all intervals, return the size of the heap. This represents the peak number of rooms needed simultaneously.
Complexity Analysis
- Time Complexity: . Sorting takes . The loop runs times. Each iteration involves a push and potentially a pop operation on the heap, which is where is the number of rooms (bounded by ). Thus, total time is dominated by sorting: .
- Space Complexity: . The heap stores at most one entry per interval in the worst case (all meetings overlap), requiring linear space.
Solution
import heapq
def minMeetingRooms(intervals):
if not intervals:
return 0
# Sort by start time to process meetings chronologically based on demand
intervals.sort(key=lambda x: x[0])
# Min-heap stores the end times of active rooms.
# Smallest element is always the earliest room that becomes free.
min_heap = []
for start, end in intervals:
if min_heap and min_heap[0] <= start:
# The earliest ending meeting has finished by now.
# Reuse this room (pop old end time) and update it with new meeting's end time.
heapq.heappop(min_heap)
# Push the current meeting's end time to represent a busy slot until 'end'
heapq.heappush(min_heap, end)
return len(min_heap)
# Example usage:
print(minMeetingRooms([[0,30],[5,10],[15,20]])) # Output: 2
Edge Cases Handled
- Empty Input: Although constraints specify
intervals.length >= 1, the code checks for empty input to return0safely. - Exact Boundary Overlap: The condition
min_heap[0] <= startcorrectly handles cases where a meeting ends at time and another starts exactly at . They share a room because there is no overlap in usage duration. - Single Interval: If only one interval exists, the heap grows to size 1 immediately; loop finishes, returns
len(heap) = 1. Correct. - All Overlapping Intervals: The heap will grow until it contains all intervals’ end times (size ), correctly returning .