LeetCode 253 Meeting Rooms II - Example and Complexity Analysis

Trace intervals = [[0,30],[5,10],[15,20]].

Events: [(0,start),(5,start),(10,end),(15,start),(20,end),(30,end)].

Sorted by time (ends before starts if same time): [(0,+1),(5,+1),(10,-1),(15,+1),(20,-1),(30,-1)].

Walk through:

• Time 0: rooms = 1.
• Time 5: rooms = 2. (max so far = 2)
• Time 10: rooms = 1.
• Time 15: rooms = 2. (max still 2)
• Time 20: rooms = 1.
• Time 30: rooms = 0.

Answer: $2$ rooms.

$O(n \log n)$ time for sorting. $O(n)$ space for events.