Meeting Rooms II

Problem

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

1 <= intervals.length <= 10^4
0 <= starti < endi <= 10^6

Solution

Approach 1: Min Heap (Priority Queue)

The key insight is to track when rooms become available using a min heap of end times.

Implementation

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

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

        # Min heap to track end times of meetings
        rooms = []

        for interval in intervals:
            # If earliest ending meeting has finished, reuse that room
            if rooms and rooms[0] <= interval[0]:
                heapq.heappop(rooms)

            # Allocate room (add end time to heap)
            heapq.heappush(rooms, interval[1])

        return len(rooms)

Approach 2: Chronological Ordering (Two Pointers)

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # Separate and sort start and end times
        start_times = sorted([i[0] for i in intervals])
        end_times = sorted([i[1] for i in intervals])

        rooms_needed = 0
        max_rooms = 0
        start_ptr = 0
        end_ptr = 0

        while start_ptr < len(intervals):
            # A meeting is starting
            if start_times[start_ptr] < end_times[end_ptr]:
                rooms_needed += 1
                max_rooms = max(max_rooms, rooms_needed)
                start_ptr += 1
            # A meeting is ending
            else:
                rooms_needed -= 1
                end_ptr += 1

        return max_rooms

Complexity Analysis

Min Heap Approach:

Time Complexity: O(n log n), where n is number of meetings. Sorting plus heap operations.
Space Complexity: O(n) for the heap in worst case (all meetings overlap).

Two Pointers Approach:

Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) for the separate start and end arrays.

Key Insights

Room Reuse: A room becomes available when a meeting ends. We can reuse it for the next meeting starting after that time.
Min Heap Strategy: Keep track of when rooms become available (end times). Always try to reuse the earliest available room.
Chronological Events: Think of each start and end as separate events. Count simultaneous active meetings.
Peak Concurrency: The answer is the maximum number of overlapping meetings at any point in time.
Two Pointers Intuition: Process events (starts and ends) in chronological order, tracking active meetings.
Greedy Choice: Always reuse the earliest available room - this minimizes total rooms needed.