{x}
blog image

Remove Interval

Solution Explanation for LeetCode 1272: Remove Interval

This problem involves manipulating a set of intervals represented as a list of [start, end) pairs. The goal is to remove a given interval from this set and return the resulting set as a sorted list of disjoint intervals.

Approach:

The most efficient approach is a linear scan through the input intervals with case analysis. For each interval [a, b) in the input list intervals, and given the interval to be removed toBeRemoved = [x, y), we consider these cases:

  1. No overlap: If b <= x or a >= y, then [a, b) and [x, y) do not overlap. We simply add [a, b) to the result.

  2. Partial overlap: If a < x and b > y, [a, b) contains [x, y). We need to split [a, b) into two non-overlapping intervals: [a, x) and [y, b), and add them to the result.

  3. Complete containment: If x <= a and b <= y, [a, b) is fully contained within [x, y). In this case, we don't add [a, b) to the result.

  4. Partial overlap (other case): If a < y and b > x, but neither condition 2 nor 3 is met, this means that the interval to be removed intersects with only part of [a, b). Then we need to split the overlapping interval. We must check which parts overlap and split according to the overlaps.

Time Complexity: O(n), where n is the number of intervals in intervals. We iterate through the list once.

Space Complexity: O(n) in the worst case, where the output list may contain up to 2n intervals (if every interval is split into two). In most cases, the space complexity is less than O(n).

Code Implementation (Python):

def removeInterval(intervals, toBeRemoved):
    x, y = toBeRemoved
    result = []
    for a, b in intervals:
        if b <= x or a >= y:  # No overlap
            result.append([a, b])
        elif a < x and b > y:  # Complete containment
            result.append([a, x])
            result.append([y, b])
        elif a < y and b > x: # Partial overlap
            if a < x:
                result.append([a,x])
            if b > y:
                result.append([y,b])
 
    return result

Code Implementation (Java):

import java.util.*;
 
class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        int x = toBeRemoved[0], y = toBeRemoved[1];
        List<List<Integer>> result = new ArrayList<>();
        for (int[] interval : intervals) {
            int a = interval[0], b = interval[1];
            if (b <= x || a >= y) { // No overlap
                result.add(Arrays.asList(a, b));
            } else if (a < x && b > y) { // Complete containment
                result.add(Arrays.asList(a, x));
                result.add(Arrays.asList(y, b));
            } else if (a < y && b > x){ //Partial Overlap
                if(a < x) result.add(Arrays.asList(a,x));
                if(b > y) result.add(Arrays.asList(y,b));
            }
        }
        return result;
    }
}

Code Implementation (C++):

#include <vector>
 
class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        int x = toBeRemoved[0], y = toBeRemoved[1];
        vector<vector<int>> result;
        for (const auto& interval : intervals) {
            int a = interval[0], b = interval[1];
            if (b <= x || a >= y) { // No overlap
                result.push_back({a, b});
            } else if (a < x && b > y) { // Complete containment
                result.push_back({a, x});
                result.push_back({y, b});
            } else if (a < y && b > x){ //Partial Overlap
                if(a < x) result.push_back({a,x});
                if(b > y) result.push_back({y,b});
            }
        }
        return result;
    }
};

The provided solutions in Python, Java, and C++ all follow this case analysis approach, ensuring linear time complexity and efficient removal of the specified interval. Remember to handle edge cases carefully to avoid errors.