193. Slot It In
A theatre's schedule is a list of intervals, each [start, end] meaning the stage is taken from start to end, both included. The list is sorted by start and no two entries share a time, so intervals[i + 1][0] > intervals[i][1] always holds.
A new show fresh = [start, end] must be added. Any existing entry that shares a time with it, directly or after merging, is absorbed, so the show and everything it touches become one entry from the earliest start to the latest end.
Return the full schedule after the show is added, still sorted by start. Do not sort the input again; use the order you are given.
Example 1
- Input:
- intervals = [[2,4],[7,9],[12,15]], fresh = [5,8]
- Output:
- [[2,4],[5,9],[12,15]]
- Explanation:
[5,8] does not touch [2,4] but overlaps [7,9], so they combine into [5,9]; [12,15] is unaffected.
Example 2
- Input:
- intervals = [[1,2],[3,4]], fresh = [2,3]
- Output:
- [[1,4]]
- Explanation:
[2,3] touches both entries (hour 2 and hour 3), so all three merge into [1,4].
Example 3
- Input:
- intervals = [[6,8]], fresh = [1,3]
- Output:
- [[1,3],[6,8]]
- Explanation:
The new show ends before the only entry starts, so it is simply placed first.
Constraints
0 ≤ intervals.length ≤ 105
0 ≤ start ≤ end ≤ 109 for every entry and for freshintervals is sorted by start with no shared times
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)
- Space
- O(n)