Problem Breakdown
We are given a sorted list of disjoint intervals representing a set of real numbers (half-open ranges [a, b)). We also have one specific interval toBeRemoved that we need to subtract from this collection. The goal is to return the remaining parts as a new sorted list of disjoint intervals.
Inputs:
intervals: A 2D array where each row represents an interval[start, end). Sorted by start time and guaranteed to be non-overlapping (disjoint).toBeRemoved: An array representing the single range[remove_start, remove_end)that must be excluded.
Outputs:
- A list of intervals representing the set difference:
(intervals - toBeRemoved). The result must remain sorted and disjoint.
Implicit Constraints & Edge Cases:
- Disjointness: Since input is already disjoint and sorted, we don’t need to merge adjacent results (e.g.,
[0,2)and[2,3)are distinct but touching; the problem treats them as separate entities unless they overlap). However, if an interval gets split bytoBeRemoved, we must ensure valid intervals (start < end) before adding. - Containment: An existing interval might be fully contained within
toBeRemoved(resulting in no output for that specific input row) or completely outside it. - Partial Overlap: The removal range cuts through an existing interval, creating a left remainder and/or a right remainder. We must handle both cases independently to avoid gaps or duplicates.
Intuition
A brute force approach would involve iterating over every number in the real line (impossible) or checking intersection for each point, which is where N is interval count and M is range size—inefficient given infinite precision requirements. Since we are dealing with intervals on a continuous domain but represented by discrete bounds, this becomes an interval arithmetic problem.
The key insight is that since intervals is sorted, we can process each one in linear time . For every interval [start, end) from the input:
- If it ends before removal starts -> Keep as is (Before).
- If it starts after removal ends -> Keep as is (After).
- Otherwise -> It overlaps with
toBeRemoved. We must split this interval into valid parts that fall outside[remove_start, remove_end):- Left Part: From current start up to the minimum of our end or removal’s start.
- Right Part: From maximum of current start and removal’s end up to current end.
Approach
- Initialize an empty result list
res. - Extract bounds from
toBeRemovedinto variables for easier comparison (r_start,r_end). - Iterate through each
[start, end]in the inputintervals:- Case A (No Overlap - Before): If
end <= r_start. The interval is completely to the left of removal. Append original interval. - Case B (No Overlap - After): If
start >= r_end. The interval is completely to the right. Append original interval. - Case C (Overlap Exists): Otherwise, we have an intersection. We need to calculate valid sub-intervals:
- Calculate potential left boundary end point:
min(end, r_start). If this value is greater thanstart, append[start, min_val]. - Calculate potential right boundary start point:
max(start, r_end). If this value is less thanend, append[right_val, end].
- Calculate potential left boundary end point:
- Case A (No Overlap - Before): If
- Return the accumulated list in
res.
Complexity Analysis
- Time Complexity: where is the number of intervals. We iterate through the input list exactly once performing constant-time arithmetic operations per interval. Sorting is not required as output order matches input order naturally due to processing sequence.
- Space Complexity: auxiliary space (excluding the space required for the result array). The logic only uses a few pointers and variables regardless of input size.
Solution
from typing import List
def removeInterval(intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
res = []
# Extract removal bounds for cleaner comparison
r_start, r_end = toBeRemoved[0], toBeRemoved[1]
for start, end in intervals:
# Case 1: Interval is completely before the removed range.
if end <= r_start:
res.append([start, end])
# Case 2: Interval is completely after the removed range.
elif start >= r_end:
res.append([start, end])
else:
# Case 3: Overlap exists. We need to split or truncate this interval.
# Check for a valid left part (before removal starts)
# The right boundary of the kept segment is min(current_end, remove_start)
if start < min(end, r_start):
res.append([start, min(end, r_start)])
# Check for a valid right part (after removal ends)
# The left boundary of this new segment is max(current_start, remove_end)
if max(start, r_end) < end:
res.append([max(start, r_end), end])
return res
Edge Cases Handled
- No Intersection: If
toBeRemovedfalls entirely outside all intervals (e.g., removal is[10, 20], interval ends at5or starts at30), the code adds them unchanged. - Full Containment: If an input interval like
[2, 8]overlaps with removal[4, 6], it splits into[2, 4)and[6, 8). If an interval is fully inside (e.g.,[3, 5]vs remove[1, 7]), both split conditions fail validity checks (start < min_val) or result in empty ranges, so nothing is added for that row. - Empty Result: If all intervals are removed by
toBeRemoved, the loop finishes without appending anything tores, returning an empty list correctly.