Problem Breakdown
We are given an array of intervals, where each interval is represented as [start, end]. The goal is to return the number of remaining intervals after removing all that are “covered” by at least one other interval. An interval covers interval if and only if AND .
Inputs: A list of lists, where each inner list contains two integers [start, end].
Outputs: An integer representing the count of non-covered intervals.
Constraints & Edge Cases:
- Empty Input: Constraints state length , so we don’t need to handle empty arrays explicitly in code logic (though good practice).
- Duplicates/Uniqueness: The problem states all intervals are unique, but our algorithm should naturally handle duplicates if they existed. If two identical intervals exist, one covers the other; sorting handles this by ensuring only one counts or both count depending on strict inequality checks. Here we use
end > max_end, so strictly greater ensures distinctness in counting logic for same bounds (though constraints say unique). - Overlapping: Intervals can overlap partially or fully. The sort order is critical here to handle overlaps efficiently without nested loops.
Intuition
A brute-force approach would compare every interval with every other interval () to check coverage conditions. While allows this, a senior engineer should aim for an optimal solution using sorting and greedy logic.
Key Insight: If we sort the intervals by their start time in ascending order, any potential covering interval must appear before or at the same index as the current interval (since it needs to have started earlier). By maintaining a running maximum of end times (max_end) seen so far during iteration:
- We know that all previous intervals satisfy
start_prev <= start_curr. - If an interval’s
endis less than or equal to the currentmax_end, it means there exists at least one previously processed interval (which started earlier) that ends later, thus covering the current interval completely. - To handle cases where intervals share the same start time correctly (e.g.,
[1,4]and[1,2]), we must sort by end time in descending order for ties. This ensures the widest interval is processed first to set a highmax_end, allowing subsequent narrower intervals starting at the same point to be identified as covered immediately.
Approach
- Sort: Sort the input list primarily by start time ascending, and secondarily by end time descending (for equal starts).
- Initialize: Set a counter for remaining intervals (
count = 0) and track the furthest right boundary seen so far (max_end). Initializemax_endto -1 or handle the first element separately since inputs are non-negative. - Iterate: Loop through each interval
[start, end]:- If
end > max_end, this interval is not covered by any previous one (since all previous ones endedmax_end). Increment count and updatemax_endto the currentend. - Otherwise (
end <= max_end), it is covered. Do nothing for the counter, but implicitly we don’t need to updatemax_endbecause a larger end would have already been seen or this one doesn’t extend coverage further than what’s tracked (though strictly speaking updating withmax(max_end, end)handles both cases safely).
- If
- Return: Return the final count.
Complexity Analysis
- Time Complexity: due to sorting. The subsequent linear scan is . Total time is dominated by sort.
- Space Complexity: auxiliary space (ignoring input storage and Python’s internal stack for Timsort).
Solution
def removeCoveredIntervals(intervals):
# Sort intervals: primary key start asc, secondary key end desc
# This ensures wider intervals starting at the same point come first.
intervals.sort(key=lambda x: (x[0], -x[1]))
count = 0
max_end = float('-inf')
for _, end in intervals:
if end > max_end:
# This interval extends beyond any previously seen coverage boundary,
# meaning it is not covered by previous intervals.
count += 1
max_end = end
return count
# Example usage matching problem description logic (not required for submission)
# print(removeCoveredIntervals([[1,4],[3,6],[2,8]]))
Edge Cases Handled
- Single Interval: The loop runs once;
end > -infis true; returns 1. Correct. - All Covered by One Large Interval (e.g.,
[0,5], [1,4]): Sorted order places large interval first. First setsmax_end. Second has smaller end max. Count remains 1. Correct. - Same Start Times: Sorting with
-x[1]ensures the largest range is processed first to establish a high coverage threshold for subsequent narrower intervals starting at that same point. - Disjoint Intervals (e.g.,
[0,2], [3,4]): Each interval has an end greater than previous max_end. Count increments every time. Correct.