1272. Remove Interval π
Description
A set of real numbers can be represented as the union of several disjoint intervals, where each interval is in the form [a, b)
. A real number x
is in the set if one of its intervals [a, b)
contains x
(i.e. a <= x < b
).
You are given a sorted list of disjoint intervals intervals
representing a set of real numbers as described above, where intervals[i] = [ai, bi]
represents the interval [ai, bi)
. You are also given another interval toBeRemoved
.
Return the set of real numbers with the interval toBeRemoved
removed from intervals
. In other words, return the set of real numbers such that every x
in the set is in intervals
but not in toBeRemoved
. Your answer should be a sorted list of disjoint intervals as described above.
Example 1:
Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6] Output: [[0,1],[6,7]]
Example 2:
Input: intervals = [[0,5]], toBeRemoved = [2,3] Output: [[0,2],[3,5]]
Example 3:
Input: intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4] Output: [[-5,-4],[-3,-2],[4,5],[8,9]]
Constraints:
1 <= intervals.length <= 104
-109 <= ai < bi <= 109
Solutions
Solution 1: Case Discussion
We denote the interval to be removed as $[x, y)$. We traverse the interval list, and for each interval $[a, b)$, there are three cases:
- $a \geq y$ or $b \leq x$, which means that this interval does not intersect with the interval to be removed. We directly add this interval to the answer.
- $a \lt x$, $b \gt y$, which means that this interval intersects with the interval to be removed. We split this interval into two intervals and add them to the answer.
- $a \geq x$, $b \leq y$, which means that this interval is completely covered by the interval to be removed. We do not add it to the answer.
The time complexity is $O(n)$, where $n$ is the length of the interval list. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|