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:

1. No Overlap: if the interval does not overlap with the interval to be removed, include it in the answer unchanged.
2. 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.
3. 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.