Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1272.html
1272. Remove Interval
Level
Medium
Description
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
For each interval in intervals, compare the interval with the interval toBeRemoved, and store the remove status for each interval.
There are 5 statuses, each of which should be dealt with in the following way.
Status 0: interval[1] <= toBeRemoved[0] || interval[0] >= toBeRemoved[1]. This status means that interval is disjoint with toBeRemoved, so simply keep interval`.
Status 1: interval[0] >= toBeRemoved[0] && interval[1] <= toBeRemoved[1]. This status means that interval is completely contained in toBeRemoved, so interval is removed.
Status 2: interval[0] < toBeRemoved[0] && interval[1] > toBeRemoved[1]. This status means that toBeRemoved is completely contained in interval. After toBeRemoved is removed, there will be two disjoint intervals, which are [interval[0], toBeRemoved[0]] and [toBeRemoved[1], interval[1]].
Status 3: interval[0] < toBeRemoved[0] && interval[1] > toBeRemoved[0] && interval[1] <= toBeRemoved[1]. After toBeRemoved is removed, only the left part of interval will be kept, and the remaining interval is [interval[0], toBeRemoved[0]].
Status 4: interval[0] >= toBeRemoved[0] && interval[0] < toBeRemoved[1] && interval[1] > toBeRemoved[1]. After toBeRemoved is removed, only the right part of interval will be kept, and the remaining interval is [toBeRemoved[1], interval[1]].
Do the corresponding operations for each interval in intervals.
Solution-2
This is also a problem that belongs to the scan line. The idea is also relatively straightforward, traverse the input array, and the sub-intervals that do not overlap the interval toBeRemoved that need to be removed are directly added to the result set.
If there is an overlap with toBeRemoved, compare the left and right boundaries of the two to find out what interval needs to be removed.
-
public class Remove_Interval { public static void main(String[] args) { Remove_Interval out = new Remove_Interval(); Solution s = out.new Solution(); System.out.println(s.removeInterval(new int[][]{ {0,2}, {3,4}, {5,7} }, new int[]{1,6})); // [[0,1],[6,7]] } // to clarify: overlap in between intervals ? if so then more complexed class Solution { public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) { List<List<Integer>> res = new ArrayList<>(); if (intervals == null || intervals.length == 0) { return res; } for (int[] i : intervals) { // no overlap if (i[1] <= toBeRemoved[0] || i[0] >= toBeRemoved[1]) { res.add(Arrays.asList(i[0], i[1])); } // i[1] > toBeRemoved[0] && i[0] < toBeRemoved[1] else { // left end no overlap if (i[0] < toBeRemoved[0]) { res.add(Arrays.asList(i[0], toBeRemoved[0])); } // right end no overlap if (i[1] > toBeRemoved[1]) { res.add(Arrays.asList(toBeRemoved[1], i[1])); } // i inside of toBeRemoved, then remove. ie no add to result list } } return res; } } } class Solution { public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) { int x = toBeRemoved[0], y = toBeRemoved[1]; List<List<Integer>> ans = new ArrayList<>(); for (var e : intervals) { int a = e[0], b = e[1]; if (a >= y || b <= x) { ans.add(Arrays.asList(a, b)); } else { if (a < x) { ans.add(Arrays.asList(a, x)); } if (b > y) { ans.add(Arrays.asList(y, b)); } } } return ans; } } -
class Solution { public: vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) { int x = toBeRemoved[0], y = toBeRemoved[1]; vector<vector<int>> ans; for (auto& e : intervals) { int a = e[0], b = e[1]; if (a >= y || b <= x) { ans.push_back(e); } else { if (a < x) { ans.push_back({a, x}); } if (b > y) { ans.push_back({y, b}); } } } return ans; } }; -
''' >>> a [1, 2, 3, 4, 5] >>> >>> x, y = a Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: too many values to unpack >>> x,y,z,p,q = a >>> x 1 >>> y 2 >>> z 3 ''' class Solution: def removeInterval( self, intervals: List[List[int]], toBeRemoved: List[int] ) -> List[List[int]]: x, y = toBeRemoved ans = [] for a, b in intervals: if a >= y or b <= x: ans.append([a, b]) else: if a < x: ans.append([a, x]) # in this else block, meaning b>x, so no need to append [a,min(b,x)] if b > y: ans.append([y, b]) # if x < a < b < y, then skip (a,b), do nothing return ans ############ class Solution: def removeInterval( self, intervals: List[List[int]], toBeRemoved: List[int] ) -> List[List[int]]: result = [] for ind, intv in enumerate(intervals): if intv[1] < toBeRemoved[0] or toBeRemoved[1] < intv[0]: result.append(intv) else: if intv[0] < toBeRemoved[0]: result.append([intv[0], min(intv[1], toBeRemoved[0])]) # min() is not needed if intv[1] > toBeRemoved[1]: result.append([max(intv[0], toBeRemoved[1]), intv[1]]) return result -
func removeInterval(intervals [][]int, toBeRemoved []int) (ans [][]int) { x, y := toBeRemoved[0], toBeRemoved[1] for _, e := range intervals { a, b := e[0], e[1] if a >= y || b <= x { ans = append(ans, e) } else { if a < x { ans = append(ans, []int{a, x}) } if b > y { ans = append(ans, []int{y, b}) } } } return }