Problem Description

The "Remove Interval" problem asks you to process a list of intervals and remove a specified interval from each of them. More specifically, you are given:

• An array intervals, where each element is an interval represented as [start, end) (inclusive of start, exclusive of end).
• A single interval toBeRemoved in the same format.

For each interval in intervals, you must remove any part that overlaps with toBeRemoved. The result is a list of intervals representing the remaining (non-overlapping) segments.

Constraints:

• Each interval in intervals and toBeRemoved is a pair of integers [a, b) with a < b.
• Intervals are non-overlapping and sorted by their start time.
• Return the result as a list of intervals, also sorted and non-overlapping.

Thought Process

The first step is to understand what it means to "remove" an interval from another. If two intervals don't overlap, nothing needs to be done. If they do overlap, we need to cut out the overlapping part. There are a few possible cases for each interval:

• The interval is completely before or after toBeRemoved — keep it as is.
• The interval partially overlaps toBeRemoved on the left or right — keep the non-overlapping part.
• The interval completely contains toBeRemoved — split it into two intervals (before and after the removed part).

Brute-force would involve checking all possible overlaps and carefully handling edge cases. But since the intervals are sorted and non-overlapping, we can process them in a single pass, checking for overlap and constructing the result accordingly.

Solution Approach

The solution works by iterating through each interval and determining how it relates to toBeRemoved. Here are the steps:

1. For each interval [start, end) in intervals:
   • If end <= removeStart or start >= removeEnd: The interval is completely outside toBeRemoved. Add it as is.
   • If start < removeStart < end: The left part of the interval is outside toBeRemoved. Add [start, removeStart).
   • If start < removeEnd < end: The right part of the interval is outside toBeRemoved. Add [removeEnd, end).
2. Be careful with intervals that both start before removeStart and end after removeEnd — both the left and right parts need to be added.
3. Return the resulting list of intervals.

This approach is efficient because it processes each interval only once and leverages the sorted, non-overlapping property of the input.

Example Walkthrough

Let's consider the following example:

• intervals = [[0,2],[3,4],[5,7]]
• toBeRemoved = [1,6]

1. Interval [0,2] overlaps with [1,6] from 1 to 2. The non-overlapping part is [0,1].
2. Interval [3,4] is completely inside [1,6], so after removal, nothing remains from this interval.
3. Interval [5,7] overlaps with [1,6] from 5 to 6. The non-overlapping part is [6,7].

The final result is [[0,1],[6,7]].

Code Implementation

class Solution:
    def removeInterval(self, intervals, toBeRemoved):
        res = []
        remove_start, remove_end = toBeRemoved
        for start, end in intervals:
            # Left part (before toBeRemoved)
            if start < remove_start < end:
                res.append([start, remove_start])
            # Right part (after toBeRemoved)
            if start < remove_end < end:
                res.append([remove_end, end])
            # Completely outside (no overlap)
            if end <= remove_start or start >= remove_end:
                res.append([start, end])
        return res
    

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> res;
        int removeStart = toBeRemoved[0], removeEnd = toBeRemoved[1];
        for (const auto& interval : intervals) {
            int start = interval[0], end = interval[1];
            // Left part
            if (start < removeStart && removeStart < end)
                res.push_back({start, removeStart});
            // Right part
            if (start < removeEnd && removeEnd < end)
                res.push_back({removeEnd, end});
            // Completely outside
            if (end <= removeStart || start >= removeEnd)
                res.push_back({start, end});
        }
        return res;
    }
};
    

class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> res = new ArrayList<>();
        int removeStart = toBeRemoved[0], removeEnd = toBeRemoved[1];
        for (int[] interval : intervals) {
            int start = interval[0], end = interval[1];
            // Left part
            if (start < removeStart && removeStart < end)
                res.add(Arrays.asList(start, removeStart));
            // Right part
            if (start < removeEnd && removeEnd < end)
                res.add(Arrays.asList(removeEnd, end));
            // Completely outside
            if (end <= removeStart || start >= removeEnd)
                res.add(Arrays.asList(start, end));
        }
        return res;
    }
}
    

var removeInterval = function(intervals, toBeRemoved) {
    const res = [];
    const [removeStart, removeEnd] = toBeRemoved;
    for (const [start, end] of intervals) {
        // Left part
        if (start < removeStart && removeStart < end)
            res.push([start, removeStart]);
        // Right part
        if (start < removeEnd && removeEnd < end)
            res.push([removeEnd, end]);
        // Completely outside
        if (end <= removeStart || start >= removeEnd)
            res.push([start, end]);
    }
    return res;
};
    

Time and Space Complexity

Brute-force Approach: For each interval, you might check all possible overlaps, which could result in O(n) time, where n is the number of intervals. However, due to the sorted, non-overlapping property, you can process each interval in constant time.

Optimized Approach:

• Time Complexity: O(n) — Each interval is processed once.
• Space Complexity: O(n) in the worst case, since the output list can have up to twice as many intervals (if every interval splits).

Summary

The "Remove Interval" problem is efficiently solved by iterating through each interval, checking for overlap with the interval to be removed, and constructing the result accordingly. By leveraging the sorted, non-overlapping property of the input, we avoid unnecessary checks and achieve a linear solution. The key insight is to carefully handle partial overlaps and split intervals when necessary, leading to a clean and elegant approach.