Leetcode 253. Meeting Rooms II

Problem

You are building a scheduling system for a company that needs to allocate conference rooms efficiently. Given a collection of meeting time intervals where each interval is represented as [start, end], determine the minimum number of conference rooms required to accommodate all meetings without any scheduling conflicts.

Each meeting occupies a room from its start time (inclusive) to its end time (exclusive). For example, a meeting from [0, 30] means the room is occupied from time 0 up to (but not including) time 30.

Requirements

1. Calculate the minimum number of rooms needed so that no two meetings overlap in the same room
2. Handle empty input appropriately (return 0 for no meetings)
3. Meetings with the same start and end times are considered overlapping
4. A meeting ending at time T does not conflict with a meeting starting at time T

Constraints

• 0 ≤ meetings.length ≤ 10,000
• Each meeting interval is represented as [start, end] where 0 ≤ start < end ≤ 1,000,000
• Target time complexity: O(n log n) where n is the number of meetings
• Target space complexity: O(n)

Examples

Example 1:

` Input: [[0, 30], [5, 10], [15, 20]] Output: 2 Explanation:

• At time 0, meeting 1 starts (1 room in use)
• At time 5, meeting 2 starts (2 rooms in use)
• At time 10, meeting 2 ends (1 room in use)
• At time 15, meeting 3 starts (2 rooms in use)
• At time 20, meeting 3 ends (1 room in use)
• At time 30, meeting 1 ends (0 rooms in use) Maximum rooms needed: 2 `

Example 2:

Input: [[7, 10], [2, 4]] Output: 1 Explanation: The meetings don't overlap, so 1 room is sufficient.

Example 3:

Input: [[1, 10], [2, 6], [3, 5], [7, 9]] Output: 3 Explanation: At time 3, three meetings are happening simultaneously: [1,10], [2,6], and [3,5].

Hint 1: Think About Events Instead of thinking about meetings as intervals, consider them as separate start and end events. What happens at each event in chronological order?

Hint 2: Tracking Active Meetings The answer is the maximum number of meetings happening at the same time. Can you track how many meetings are "active" as you process events chronologically?

Hint 3: Min-Heap Approach Sort meetings by start time. Use a min-heap to track end times of ongoing meetings. When starting a new meeting, remove all meetings from the heap that have already ended. The heap size tells you how many rooms are currently in use.

Full Solution `` Alternative Solution: Event-Based Sweep Line

` def minMeetingRooms(meetings): """ Event-based approach: track start and end events separately.

Time: O(n log n)
Space: O(n)
"""
if not meetings:
    return 0

# Create separate lists for start and end times
starts = sorted([m[0] for m in meetings])
ends = sorted([m[1] for m in meetings])

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

# Process all events in chronological order
while start_ptr < len(meetings):
    if starts[start_ptr] < ends[end_ptr]:
        # A meeting starts - need another room
        rooms_needed += 1
        max_rooms = max(max_rooms, rooms_needed)
        start_ptr += 1
    else:
        # A meeting ends - free up a room
        rooms_needed -= 1
        end_ptr += 1

return max_rooms

`

Complexity Analysis:

• Time Complexity: O(n log n) where n is the number of meetings. Dominated by sorting the meetings or event times.
• Space Complexity: O(n) for the heap (min-heap approach) or for storing start/end times separately (sweep line approach).

Key Insights:

1. The answer equals the maximum number of overlapping meetings at any point in time
2. Sorting by start time allows us to process meetings in chronological order
3. A min-heap efficiently tracks which meetings are currently active by their end times
4. The sweep line approach processes start and end events separately, counting active meetings