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;
}
}
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;
}
}
}