252. Meeting Rooms

Summary

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], determine whether a person could attend all meetings.

Example 1:

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

Example 2:

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

Approach

The key idea is to keep track of the meeting that ends last among the active meetings. If the next meeting starts before the current meeting ends, the meetings overlap. Otherwise, there is no overlap.

We can keep that end time with a heap.

The heap item looks like:

(-end)

When we get a new meeting (new_start, new_end), if new_start < -heap[0], we found an overlap, so we add -new_end to the heap. Otherwise, we replace the heap root with -new_end.

Function

Initialization:

heap = []
Sort intervals by start time.

If intervals is empty: return True

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

Return len(heap) == 1 # 1 means no overlap.

Complexity

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