Leetcode 1272. Remove Interval
Problem Explanation
We are given a sorted list of disjoint intervals and another interval which needs to be removed from the list. The output should be the sorted list of intervals after removing the specified interval.
Removing an interval means, for every interval in the list, if it overlaps with the interval to be removed, we cut it off from the overlapping section. If a single interval in the list is divided into two separated intervals because of this process, both of them would be in the new list. The idea here is to iterate over every interval in the list and see if it falls in any of these three categories:
- No Overlap: if the interval does not overlap with the interval to be removed, include it in the answer unchanged.
- Partial Overlap: if the interval is partially overlapped with the interval to be removed, cut off the intersecting part and include the remaining part(s) in the answer.
- Full Overlap: if the interval is fully overlapped with the interval to be removed, exclude it from the answer as it was fully removed.
Let's walkthrough the algorithm with the help of an example:
intervals = [[0,2],[3,4],[5,7]]
, toBeRemoved = [1,6]
The interval [0,2] partially overlaps with [1,6]. After removal, interval [0,1] is left, which is added to the answer list. The interval [3,4] fully overlaps, so nothing from this interval is added. The interval [5,7] partially overlaps and we get [6,7] after removing the overlapping part. The final list of intervals after all removals: [[0,1],[6,7]]
.
Python Solution
1 2python 3class Solution: 4 def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]: 5 res = [] 6 for interval in intervals: 7 if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]: # No overlap 8 res.append(interval) 9 else: 10 if interval[0] < toBeRemoved[0]: # if the current interval starts before the one to be removed 11 res.append([interval[0], toBeRemoved[0]]) 12 if interval[1] > toBeRemoved[1]: # if the current interval ends after the one to be removed 13 res.append([toBeRemoved[1], interval[1]]) 14 return res
Java Solution
1
2java
3class Solution {
4 public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
5 List<List<Integer>> res = new ArrayList<>();
6 int start = toBeRemoved[0], end = toBeRemoved[1];
7 for (int[] interval : intervals) {
8 if (interval[1] <= start || interval[0] >= end) {
9 res.add(Arrays.asList(interval[0], interval[1]));
10 } else {
11 if (interval[0] < start)
12 res.add(Arrays.asList(interval[0], start));
13 if (interval[1] > end)
14 res.add(Arrays.asList(end, interval[1]));
15 }
16 }
17 return res;
18 }
19}
JavaScript Solution
1 2javascript 3var removeInterval = function(intervals, toBeRemoved) { 4 let result = []; 5 let [start, end] = toBeRemoved; 6 7 for(const [curStart, curEnd] of intervals){ 8 if( curEnd <= start || curStart >= end ){ 9 result.push([curStart, curEnd]); 10 }else{ 11 if( curStart < start ){ 12 result.push([curStart, start]); 13 } 14 if( curEnd > end ){ 15 result.push([end, curEnd]); 16 } 17 } 18 } 19 return result; 20};
C++ Solution
1 2cpp 3class Solution { 4public: 5 vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) { 6 vector<vector<int>> res; 7 for(auto interval : intervals) { 8 if(interval[0] >= toBeRemoved[1] || interval[1] <= toBeRemoved[0]) { 9 res.push_back(interval); 10 } else { 11 if(interval[0] < toBeRemoved[0]) 12 res.push_back({interval[0], toBeRemoved[0]}); 13 if(interval[1] > toBeRemoved[1]) 14 res.push_back({toBeRemoved[1], interval[1]}); 15 } 16 } 17 return res; 18 } 19};
C# Solution
1 2csharp 3public class Solution { 4 public int[][] RemoveInterval(int[][] intervals, int[] toBeRemoved) { 5 6 List<int[]> ans = new List<int[]>(); 7 for(int i=0; i<intervals.Length; ++i){ 8 int start1 = intervals[i][0]; 9 int end1 = intervals[i][1]; 10 int start2 = toBeRemoved[0]; 11 int end2 = toBeRemoved[1]; 12 if(end1 <= start2 || start1 >= end2){ 13 //If there is NO overlap. We simply add the current interval to our answer 14 ans.Add(new []{start1, end1}); 15 } else { 16 if(start1 < start2) 17 //part of the current interval is to the LEFT of "toBeRemoved" 18 ans.Add(new []{start1, start2}); 19 if(end1 > end2) 20 //part of the current interval is to the RIGHT of "toBeRemoved" 21 ans.Add(new []{end2, end1}); 22 } 23 } 24 return ans.ToArray(); 25 } 26}
Ruby Solution
1 2ruby 3def remove_interval(intervals, to_be_removed) 4 result = [] 5 start, ending = to_be_removed 6 7 intervals.each do |cur_start, cur_end| 8 if cur_end <= start || cur_start >= ending 9 result << [cur_start, cur_end] 10 else 11 result << [cur_start, start] if cur_start < start 12 result << [ending, cur_end] if cur_end > ending 13 end 14 end 15 16 result 17end
Go Solution
1 2go 3func removeInterval(intervals [][]int, toBeRemoved []int) [][]int { 4 res := make([][]int, 0) 5 start, end := toBeRemoved[0], toBeRemoved[1] 6 7 for _, interval := range intervals { 8 if interval[1] <= start || interval[0] >= end { 9 res = append(res, interval) 10 } else { 11 if interval[0] < start { 12 res = append(res, []int{interval[0], start}) 13 } 14 if interval[1] > end { 15 res = append(res, []int{end, interval[1]}) 16 } 17 } 18 } 19 20 return res 21}
Each of these solutions first checks whether the current interval from the list has no overlap with the interval to be removed. If so, it is added to the result list as is. If the interval has a partial overlap, either on the left side, the right side, or both sides, the non-overlapping parts are added to the result list. This is achieved by comparing the start and end points of the current interval and the interval to be removed. The solutions differ in syntax and specific API usage according to the programming language, but the underlying logic is the same. The time complexity for all solutions is O(N), where N is the size of the intervals list, as we are just iterating through the list once.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.