192. Merge the Bookings
A studio keeps a list of room bookings. Each booking intervals[i] = [start, end] reserves every whole hour from start to end, both included. The list is in no particular order.
Two bookings are linked when they share at least one hour, so [10, 12] and [12, 15] are linked because both hold hour 12. Merge every group of linked bookings, directly or through a chain, into a single booking that runs from the earliest start to the latest end of the group.
Return the merged bookings as a list of [start, end] pairs, sorted by start. No two returned bookings may share an hour.
Example 1
- Input:
- intervals = [[4,9],[1,3],[2,5],[12,14]]
- Output:
- [[1,9],[12,14]]
- Explanation:
Bookings [1,3], [2,5] and [4,9] chain together (they share hours 2 and 4 to 5), forming [1,9]. [12,14] stands alone.
Example 2
- Input:
- intervals = [[10,12],[12,15],[20,21]]
- Output:
- [[10,15],[20,21]]
- Explanation:
[10,12] and [12,15] both contain hour 12, so they merge into [10,15]; [20,21] is separate.
Example 3
- Input:
- intervals = [[7,7]]
- Output:
- [[7,7]]
- Explanation:
A single booking is returned unchanged.
Constraints
1 ≤ intervals.length ≤ 105
0 ≤ start ≤ end ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)