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
.
-
class Solution { public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) { int length = intervals.length; int removeBegin = toBeRemoved[0], removeEnd = toBeRemoved[1]; int[] remove = new int[length]; for (int i = 0; i < length; i++) { int[] interval = intervals[i]; if (interval[1] <= removeBegin || interval[0] >= removeEnd) remove[i] = 0; else if (interval[0] >= removeBegin && interval[1] <= removeEnd) remove[i] = 1; else if (interval[0] < removeBegin && interval[1] > removeEnd) remove[i] = 2; else if (interval[0] < removeBegin && interval[1] > removeBegin) remove[i] = 3; else if (interval[0] < removeEnd && interval[1] > removeEnd) remove[i] = 4; } List<List<Integer>> remainIntervals = new ArrayList<List<Integer>>(); for (int i = 0; i < length; i++) { int[] interval = intervals[i]; int removeStatus = remove[i]; if (removeStatus == 0) { List<Integer> intervalList = new ArrayList<Integer>(); intervalList.add(interval[0]); intervalList.add(interval[1]); remainIntervals.add(intervalList); } else if (removeStatus == 2) { List<Integer> intervalList1 = new ArrayList<Integer>(); intervalList1.add(interval[0]); intervalList1.add(removeBegin); remainIntervals.add(intervalList1); List<Integer> intervalList2 = new ArrayList<Integer>(); intervalList2.add(removeEnd); intervalList2.add(interval[1]); remainIntervals.add(intervalList2); } else if (removeStatus == 3) { List<Integer> intervalList = new ArrayList<Integer>(); intervalList.add(interval[0]); intervalList.add(removeBegin); remainIntervals.add(intervalList); } else if (removeStatus == 4) { List<Integer> intervalList = new ArrayList<Integer>(); intervalList.add(removeEnd); intervalList.add(interval[1]); remainIntervals.add(intervalList); } } return remainIntervals; } }
-
Todo
-
print("Todo!")
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; } } }
-
Todo
-
print("Todo!")