234. Cut Out a Range
A city reserves stretches of a long road for roadworks. Each reservation intervals[i] = [a, b) is half-open: it includes position a but not position b. The reservations are sorted and never overlap.
An emergency now takes over the half-open range cut = [c, d), and every part of every reservation inside that range must be given up. A reservation can survive whole, be trimmed on one side, be split into two pieces around the cut, or vanish completely. Return the remaining pieces as a sorted list of half-open intervals. Never return an empty piece (one with start >= end).
Process the reservations one at a time in the given order, so the output is in the same order as the input, a left piece before a right piece. Read the constraints for what happens with unusual input.
Example 1
- Input:
- intervals = [[0,5],[8,12],[15,20]], cut = [3,10]
- Output:
- [[0,3],[10,12],[15,20]]
- Explanation:
[0,5) is trimmed to [0,3). [8,12) loses [8,10) and becomes [10,12). [15,20) is untouched.
Example 2
- Input:
- intervals = [[2,4],[6,9]], cut = [4,6]
- Output:
- [[2,4],[6,9]]
- Explanation:
The cut [4,6) sits exactly in the gap between the two reservations, so nothing is removed.
Example 3
- Input:
- intervals = [[1,10]], cut = [4,6]
- Output:
- [[1,4],[6,10]]
- Explanation:
The cut is in the middle of the only reservation, which splits into [1,4) and [6,10).
Example 4
- Input:
- intervals = [[3,5],[7,8],[9,14]], cut = [2,12]
- Output:
- [[12,14]]
- Explanation:
[3,5) and [7,8) lie fully inside [2,12) and vanish. [9,14) keeps its tail [12,14).
Constraints
0 ≤ intervals.length ≤ 2 × 105
0 ≤ a < b ≤ 109 for every reservation, sorted by a, non-overlapping
cut.length == 2, 0 ≤ c ≤ d ≤ 109
Robustness: an interval with a ≥ b is treated as empty and dropped, and if c ≥ d nothing is cut. Each interval is handled independently in the given order.
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)