Remove Interval

Problem Statement

A real number can belong to one or more intervals denoted as [a, b), where it is included in the interval if a <= x < b. Consider you have several such intervals, essentially forming a set of real numbers. These intervals are provided to you in a sorted list called intervals, where each interval [ai, bi] signifies a range from ai to bi (excluding bi). Alongside, you are given another interval called toBeRemoved. The task is to calculate a new set of intervals representing real numbers that belong to the original intervals but do not overlap with toBeRemoved. The resulting list of intervals should also be sorted and follow the similar disjoint format.

Examples

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]]

Example 3

Input:

intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]

Output:

[[-5,-4],[-3,-2],[4,5],[8,9]]

Constraints

• 1 <= intervals.length <= 104
• -109 <= ai < bi <= 109

Approach and Intuition

1. Understand Interval Manipulation:

   • Each interval [a, b) includes elements from a up to, but not including, b.
   • If an element x lies within this interval, it must satisfy a <= x < b.

2. Handling the Removal Process:

   • For each interval in the intervals list, consider the relationship between the interval and the toBeRemoved interval.
   • There are a few scenarios to consider:
     • The interval is entirely outside the toBeRemoved range, in which case it remains unchanged.
     • The interval is entirely within the toBeRemoved range, in which case it is omitted.
     • The interval overlaps with part of the toBeRemoved interval, in which case it needs to be truncated or split into two.

3. Processing Edges and Overlaps:

   • Begin by iterating through each interval:
     • Compare the start and end of the interval with the start and end of toBeRemoved.
     • Depending on where the overlap occurs, if any, adjust the current interval:
       • No overlap: output the interval as is.
       • Overlap at the start: truncate the start of the interval.
       • Overlap at the end: truncate the end of the interval.
       • Overlap covers the interval: omit this interval entirely.
       • Partial coverage by toBeRemoved at both ends: split the interval into two at the points where toBeRemoved starts and ends.

4. Efficiency Considerations:

   • Since the intervals list is sorted, you can proceed sequentially and adjust intervals without needing to re-sort.
   • The operations involved are straightforward checks and potential cuts, making the overall process efficient.

By systematically analyzing and adjusting each interval in relation to the toBeRemoved interval, you can derive the final list of intervals that excludes any numbers that fall within the toBeRemoved range.

Solutions

class Solution {
    public List<List<Integer>> filterIntervals(int[][] intervals, int[] remove) {
        List<List<Integer>> output = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[0] > remove[1] || interval[1] < remove[0]) {
                output.add(Arrays.asList(interval[0], interval[1]));
            } else {
                if (interval[0] < remove[0]) {
                    output.add(Arrays.asList(interval[0], remove[0]));
                }
                if (interval[1] > remove[1]) {
                    output.add(Arrays.asList(remove[1], interval[1]));
                }
            }
        }
        return output;
    }
}

class Solution:
    def filterIntervals(self, ranges: List[List[int]], removalRange: List[int]) -> List[List[int]]:
    
        begin_removal, end_removal = removalRange
        result = []
    
        for start, end in ranges:
            # Verify if the current interval is unaffected
            if start > end_removal or end < begin_removal:
                result.append([start, end])
            else:
                # Check if there's a left subinterval to retain
                if start < begin_removal:
                    result.append([start, begin_removal])
                # Check if there's a right subinterval to retain
                if end > end_removal:
                    result.append([end_removal, end])
    
        return result