253. Meeting Rooms II

Summary

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

Approach

If we find overlapping meetings, we need another room. If meetings do not overlap, we do not need another room.

We need to track the meeting that ends first among the active meetings.

If the incoming meeting does not overlap with the meeting that ends first, pop the heap root and insert the new meeting end time. Otherwise, just push the new meeting because it overlaps.

If meetings overlap, the heap grows. If they do not overlap, we reuse a room by replacing the earliest end time.

So we can use a min-heap.

Function

Initialization:

heap = []
Sort intervals by start time.

If intervals is empty: return 0

For start, end in intervals: If heap is empty: heap.append(end) continue If start < heap[0]: Push end to the heap. else: Pop the heap root and push end.

Return len(heap).

Complexity

Time Complexity: O(N log N) Space Complexity: O(N)