bookings is a list of closed intervals [start, end], sorted by start, pairwise disjoint and non-touching. Insert new = [s, e] and return the resulting calendar as a sorted list of disjoint closed intervals. Two intervals that overlap or touch (share at least one point, e.g. [1, 3] and [3, 5]) must be merged.
Examples
Input: bookings = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: [4, 8] overlaps [3, 5] and [6, 7] and touches [8, 10]; they all become [3, 10].
Input: bookings = [[1, 5]], new = [2, 3]
Output: [[1, 5]]
Constraints
0 <= len(bookings) <= 5 * 10**4,0 <= start <= end <= 10**9.- The result must be a list of lists.
- Target complexity: O(n).
Goals
- Split the sorted list into before, overlapping and after parts
- Grow the new interval while absorbing everything it overlaps or touches
- Return a fresh list without mutating the input