435. Non-overlapping Intervals
Model: qwen3.5:9b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 43.8%
Problem Breakdown
We are given an array of time slots (intervals) defined by [start, end]. The objective is to remove the minimum number of these intervals so that no two remaining intervals overlap.
Key constraints and definitions:
- Overlap: Two intervals and overlap if they share any common point strictly inside their range (i.e., ).
- Touching is allowed: If one interval ends at 2 (
[1,2]) and another starts at 2 ([2,3]), they do not overlap. - Goal Transformation: Minimizing the number of removed intervals is mathematically equivalent to maximizing the number of kept (non-overlapping) intervals. If we find non-overlapping intervals can be kept out of a total of , then the answer is simply .
- Edge Cases: Empty input list, single interval, negative coordinates, and duplicate intervals all need to be handled naturally by our logic without special
ifblocks.
Intuition
If we try every possible combination of removals (brute force), that would involve checking subsets or dynamic programming which is too slow ().
The key insight here comes from the Interval Scheduling Maximization problem pattern: To fit as many non-overlapping intervals as possible, we should prioritize picking intervals that finish earliest. Why? Because an interval ending earlier leaves more “room” for subsequent intervals to start without overlapping.
So, instead of sorting by start time (which might pick a long interval early and block others), we sort by end time. This greedy strategy ensures that whenever we have a choice between two compatible intervals, picking the one with the smallest end point is always optimal for future compatibility.
Approach
- Sort: Sort all intervals based on their
endvalue in ascending order. If ends are equal, secondary sort by start doesn’t strictly matter but keeps consistency. - Iterate & Count Kept: Initialize a counter for kept intervals (
count) and track the end time of the last accepted interval (last_end). - Greedy Selection: Loop through the sorted list:
- If the current interval’s start is greater than or equal to
last_end, it doesn’t overlap with our previous selection. We keep this interval, updatelast_endto the current end time, and incrementcount. - Otherwise (if there is an overlap), we implicitly “remove” this interval by skipping it in our count of kept intervals.
- If the current interval’s start is greater than or equal to
- Calculate Result: Return total number of intervals minus
count.
Complexity Analysis
- Time Complexity: , dominated by the sorting step where is the number of intervals. The linear scan takes .
- Space Complexity: auxiliary space (excluding input storage), assuming an in-place sort or ignoring the stack overhead for Timsort which Python uses ().
Solution
def eraseOverlapIntervals(intervals):
if not intervals:
return 0
# Sort by end time to prioritize finishing early (Greedy)
intervals.sort(key=lambda x: x[1])
kept_count = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
# No overlap with the previously selected interval
kept_count += 1
last_end = end
return len(intervals) - kept_count
Edge Cases Handled
- Empty Input: Returns
0immediately. - Single Interval: Loop runs once, keeps it (
kept_count=1), returns . - Touching Intervals (e.g.,
[1,2],[2,3]): Since condition isstart >= last_end, a start of 2 against an end of 2 passes the check. They are kept as non-overlapping. - Duplicate Intervals: If multiple identical intervals exist, only one will satisfy the
last_endconstraint (the first one encountered after sorting), and subsequent duplicates will be skipped/removed correctly.