Given a sorted list of disjoint intervals
, each interval intervals[i] = [a, b]
represents the set of real numbers x
such that a <= x < b
.
We remove the intersections between any interval in intervals
and the interval toBeRemoved
.
Return a sorted list of intervals
after all such removals.
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]]
Constraints:
1 <= intervals.length <= 10^4
-10^9 <= intervals[i][0] < intervals[i][1] <= 10^9
Solution: Geometry
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& r) { vector<vector<int>> ans; for (const auto& i : intervals) // Does not intersect if (i[1] <= r[0] || i[0] >= r[1]) ans.push_back(i); else { // i starts first if (i[0] < r[0]) ans.push_back({i[0], r[0]}); // i ends later if (i[1] > r[1]) ans.push_back({r[1], i[1]}); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment