Leetcode 253. Meeting Rooms II

Let's understand what we're being asked to do. We have a list of meeting time intervals like [[0,30], [5,10], [15,20]], where each interval [start, end] represents a meeting that starts at time start and ends at time end.

We need to determine the minimum number of conference rooms required so that no two meetings overlap in the same room. For example, with [[0,30], [5,10], [15,20]], at time 5 we have two meetings happening simultaneously (the [0,30] meeting and the [5,10] meeting), so we need at least 2 rooms.

Key constraint: Meetings are represented as intervals with start and end times. If one meeting ends exactly when another starts (e.g., [0,10] and [10,20]), they can use the same room (no overlap).

Edge cases to consider: What if all meetings happen at different times (need only 1 room)? What if all meetings overlap completely (need as many rooms as meetings)? What if the intervals list is empty?

The brute force approach checks every pair of meetings to see if they overlap. For each meeting, count how many other meetings it overlaps with. The maximum overlap count plus one gives the minimum rooms needed. This requires comparing every meeting with every other meeting, leading to quadratic time complexity. While simple to understand, this approach becomes impractical for large numbers of meetings.

def min_meeting_rooms(intervals):
    """
    Brute force approach: For each meeting, count how many other meetings
    it overlaps with. The maximum overlap count gives minimum rooms needed.
    Time: O(n^2), Space: O(1)
    """
    if not intervals:
        return 0
    
    max_rooms = 0
    
    # For each meeting, count overlaps with all other meetings
    for i in range(len(intervals)):
        overlap_count = 1  # Count the meeting itself
        
        # Compare with every other meeting
        for j in range(len(intervals)):
            if i != j:
                # Check if meetings overlap
                # Two intervals [a,b] and [c,d] overlap if a < d and c < b
                if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                    overlap_count += 1
        
        # Track maximum overlaps seen
        max_rooms = max(max_rooms, overlap_count)
    
    return max_rooms

The number of rooms needed at any moment equals the number of meetings happening simultaneously at that moment.

The answer is the maximum number of concurrent meetings across all time points. If we track when meetings start and end, we can count how many are active at each moment.

Instead of checking every pair of meetings for overlap (which would be O(n²)), we can process all start and end times in chronological order.

When we encounter a start time, one more room is needed. When we encounter an end time, one room becomes available. The peak concurrent count tells us the minimum rooms required.

Imagine you're managing a building's conference rooms in real-time. You have a counter showing 'Rooms Currently In Use'.

As each meeting starts, increment the counter. As each meeting ends, decrement it. The highest value the counter reaches throughout the day is the minimum number of rooms you need to build.

This is like a 'sweep line' moving through time, tracking the maximum overlap at any point.

The optimal approach uses a sweep-line algorithm with event processing. Separate all start and end times into events, then sort them chronologically. Process events in order: increment a counter for each start event, decrement for each end event. Track the maximum counter value reached, which represents the peak number of concurrent meetings. Alternatively, use a min-heap to track meeting end times: sort meetings by start time, and for each meeting, remove all ended meetings from the heap before adding the current meeting's end time. The heap size represents rooms needed.

def min_meeting_rooms(intervals):
    """
    Find minimum number of conference rooms required.
    Uses sweep-line algorithm with start/end events.
    """
    # Handle edge case
    if not intervals:
        return 0
    
    # Create events: (time, type) where type=1 for start, type=-1 for end
    events = []
    
    # Build events list from intervals
    for start, end in intervals:
        events.append((start, 1))  # Meeting starts, need +1 room
        events.append((end, -1))   # Meeting ends, free -1 room
    
    # Sort events by time (if same time, process ends before starts)
    events.sort(key=lambda x: (x[0], x[1]))
    
    # Track current rooms in use and maximum rooms needed
    current_rooms = 0
    max_rooms = 0
    
    # Process each event in chronological order
    for time, event_type in events:
        # Update current room count
        current_rooms += event_type
        
        # Track maximum concurrent meetings
        max_rooms = max(max_rooms, current_rooms)
    
    return max_rooms

• Min-heap for tracking active intervals: When dealing with overlapping intervals, use a min-heap to track end times of ongoing events - this allows O(log n) insertion/removal to efficiently determine when resources become available, making it perfect for scheduling and resource allocation problems.
• Sweep-line algorithm pattern: Transform interval problems into point events (start/end) and process them chronologically - this converts a 2D interval problem into a 1D timeline problem where you track the current count of active intervals at each event.
• Sort by start time first: Always sort intervals by start time as your first step - this ensures you process meetings in chronological order and can make greedy decisions about room allocation without missing earlier conflicts.
• Heap size equals resource count: The maximum heap size during processing directly represents the answer - when a new meeting starts, add its end time to the heap; when the earliest ending meeting finishes (heap top ≤ current start), reuse that room by popping and pushing the new end time.
• Two-pointer event processing: An alternative to heaps is creating separate sorted arrays of start and end times, then using two pointers to track when meetings begin vs. end - increment room count on starts, decrement on ends, tracking the maximum concurrent count.
• Real-world resource scheduling: This pattern applies to any resource allocation problem - CPU scheduling, airport runway management, classroom scheduling, or server request handling - wherever you need to determine minimum resources to handle overlapping demands without conflicts.