Problem Description

You are given a sorted list of disjoint intervals where each interval is represented as [a, b), meaning it includes a but excludes b. These intervals represent a set of real numbers - a number x belongs to the set if a <= x < b for at least one interval.

You need to remove another interval toBeRemoved from this set and return the resulting intervals.

Key Points:

• The input intervals are disjoint (non-overlapping) and sorted
• Each interval uses half-open notation [a, b) where a is included but b is excluded
• You must remove all numbers that fall within toBeRemoved from the original intervals
• The output should also be a sorted list of disjoint intervals

Example scenarios when removing an interval:

1. If an original interval doesn't overlap with toBeRemoved, it remains unchanged
2. If an original interval is completely inside toBeRemoved, it gets removed entirely
3. If an original interval partially overlaps with toBeRemoved, it gets split into one or two smaller intervals

The solution iterates through each interval [a, b) and compares it with toBeRemoved = [x, y):

• If a >= y or b <= x: No overlap, keep the interval as is
• If a < x and b > x: The interval extends before toBeRemoved, so keep the part [a, x)
• If a < y and b > y: The interval extends after toBeRemoved, so keep the part [y, b)
• If the interval is completely covered by toBeRemoved, it's removed (not added to the result)

Intuition

When we need to remove an interval from a set of intervals, we can think of it like cutting out a section from multiple line segments. For each original interval, we need to determine how it relates to the "cut" we're making.

The key insight is that for any interval [a, b) and the removal interval [x, y), there are only a few possible relationships:

1. No overlap: The intervals don't touch at all. This happens when the original interval ends before the removal starts (b <= x) or starts after the removal ends (a >= y). In this case, we keep the original interval unchanged.

2. Partial overlap: The removal "cuts" through the original interval. This creates two scenarios:

   • The original interval starts before the removal (a < x): We keep the left portion [a, x)
   • The original interval ends after the removal (b > y): We keep the right portion [y, b)
   • If both conditions are true, we get two pieces: [a, x) and [y, b)

3. Complete overlap: The removal completely covers the original interval. This means the entire interval disappears.

The beauty of this approach is that we can handle all cases in a single pass through the intervals. Since the intervals are already sorted and disjoint, we don't need to worry about merging results or maintaining order - we can simply process each interval independently and append the resulting pieces to our answer.

The condition checks in the code elegantly handle all these cases:

• First, we check if there's no overlap at all (a >= y or b <= x)
• If there is overlap, we check which parts of the original interval survive:
  • The left part survives if a < x
  • The right part survives if b > y

This approach naturally handles the case where an interval is completely consumed (neither condition for surviving parts is met) by simply not adding anything to the result.

Solution Approach

The implementation follows a straightforward case-by-case analysis as described in the reference approach. Let's walk through the algorithm step by step:

Algorithm Steps:

1. Extract the removal interval boundaries: We first extract x and y from toBeRemoved, representing the interval [x, y) to be removed.

2. Initialize result list: Create an empty list ans to store the resulting intervals after removal.

3. Process each interval: For each interval [a, b) in the input list, we determine its relationship with [x, y):

   • Case 1: No intersection (a >= y or b <= x)
     • The interval is completely outside the removal range
     • Add the entire interval [a, b] to the answer unchanged
   • Case 2: Intersection exists (when Case 1 is false)
     • Check if the left part survives: If a < x, add [a, x] to the answer
     • Check if the right part survives: If b > y, add [y, b] to the answer
     • Note: Both conditions can be true simultaneously, resulting in the interval being split into two parts

Key Implementation Details:

• The algorithm processes intervals in order, maintaining the sorted property naturally
• No additional data structures are needed beyond the result list
• Time complexity: O(n) where n is the number of intervals, as we process each interval exactly once
• Space complexity: O(1) for the algorithm itself (not counting the output array)

Why this approach works:

The solution leverages the fact that the input intervals are disjoint and sorted. This means:

• We can process each interval independently without worrying about overlaps between different input intervals
• The output will automatically be sorted since we process intervals in order
• Each interval can contribute at most 2 intervals to the output (when split by the removal)

The elegance of this solution lies in its simplicity - by handling just two main cases (no overlap vs. overlap), and within the overlap case checking which parts survive, we cover all possible scenarios without complex logic or edge case handling.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Input:

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

We need to remove the range [1,6) from our intervals.

Step-by-step processing:

Interval 1: [0,2)

• Compare with toBeRemoved [1,6):
• Is 0 >= 6 or 2 <= 1? No, so there IS overlap
• Check left part: Is 0 < 1? Yes, so we keep [0,1)
• Check right part: Is 2 > 6? No, so no right part survives
• Result so far: [[0,1)]

Interval 2: [3,4)

• Compare with toBeRemoved [1,6):
• Is 3 >= 6 or 4 <= 1? No, so there IS overlap
• Check left part: Is 3 < 1? No, so no left part survives
• Check right part: Is 4 > 6? No, so no right part survives
• This interval is completely removed!
• Result so far: [[0,1)]

Interval 3: [5,7)

• Compare with toBeRemoved [1,6):
• Is 5 >= 6 or 7 <= 1? No, so there IS overlap
• Check left part: Is 5 < 1? No, so no left part survives
• Check right part: Is 7 > 6? Yes, so we keep [6,7)
• Result so far: [[0,1), [6,7)]

Final output: [[0,1), [6,7)]

Visual representation:

Original:    [0====2)     [3==4)     [5====7)
ToBeRemoved:      [1==================6)
Result:      [0=1)                    [6==7)

This example demonstrates all three scenarios:

1. Interval [0,2) partially overlaps - we keep the left portion
2. Interval [3,4) is completely covered - it's removed entirely
3. Interval [5,7) partially overlaps - we keep the right portion

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the intervals list. The algorithm iterates through each interval in the input list exactly once. For each interval, it performs constant-time operations: comparing boundaries with the toBeRemoved interval and potentially appending up to two new intervals to the result list. Since we visit each interval once and perform O(1) operations per interval, the overall time complexity is O(n).

The space complexity is O(1) for auxiliary space. While the output list ans can contain up to 2n intervals in the worst case (when each original interval is split into two parts), this space is required for the output and is not considered auxiliary space. The only extra space used by the algorithm consists of the variables x, y, a, and b, which are constant regardless of the input size. Therefore, the auxiliary space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusion Between Interval Notation: [a, b) vs [a, b]

The problem statement uses half-open interval notation [a, b) where a is included but b is excluded. However, the actual implementation often uses closed intervals [a, b] where both endpoints are included. This inconsistency can lead to off-by-one errors.

The Pitfall:

• Misunderstanding whether the intervals are inclusive or exclusive at endpoints
• Incorrectly handling boundary conditions when intervals touch but don't overlap
• For example, if using [a, b) notation, intervals [1, 3) and [3, 5) don't overlap, but with [a, b] notation, [1, 3] and [3, 5] do overlap at point 3

Solution: Be consistent with your interval representation throughout the solution. If the problem uses [a, b] (closed intervals), ensure your comparisons reflect this:

# For closed intervals [a, b], no overlap condition becomes:
if interval_start > remove_end or interval_end < remove_start:
    # No overlap

2. Incorrectly Handling Interval Splitting

When an interval needs to be split into two parts (the interval extends both before and after the removal interval), developers might accidentally add only one part or use wrong boundaries.

The Pitfall:

# WRONG: Using 'elif' instead of separate 'if' statements
if interval_start < remove_start:
    result.append([interval_start, remove_start])
elif interval_end > remove_end:  # This won't execute if first condition is true!
    result.append([remove_end, interval_end])

Solution: Use independent if statements to check both conditions:

# CORRECT: Both parts can be added when interval spans the removal
if interval_start < remove_start:
    result.append([interval_start, remove_start])
if interval_end > remove_end:  # Independent check
    result.append([remove_end, interval_end])

3. Modifying Boundaries Incorrectly During Split

When splitting intervals, using the wrong boundary values (e.g., using remove_start - 1 or remove_end + 1 unnecessarily) can create gaps or overlaps in the result.

The Pitfall:

# WRONG: Creating gaps by adjusting boundaries incorrectly
if interval_start < remove_start:
    result.append([interval_start, remove_start - 1])  # Creates gap!

Solution: Use the exact boundary values without adjustment:

# CORRECT: Precise boundary handling
if interval_start < remove_start:
    result.append([interval_start, remove_start])  # Exact boundary

4. Not Handling Edge Cases Properly

Failing to consider edge cases where the removal interval extends beyond all intervals or doesn't intersect with any interval at all.

The Pitfall: Assuming the removal interval will always intersect with at least one interval, or that it falls within the bounds of the existing intervals.

Solution: The algorithm naturally handles these cases:

• If toBeRemoved doesn't intersect with any interval, all intervals are kept unchanged
• If toBeRemoved covers all intervals, the result will be an empty list
• No special edge case handling is needed if the logic is correct