Given an array of intervals, return the minimum number of intervals you'd need to remove so that the rest don't overlap each other.
Example
Input intervals = [[1,2],[2,3],[3,4],[1,3]]
Output 1
Key Pointers
This is a classic greedy interval-scheduling problem — sort by end time, not start time.
Sorting by end time means you always keep whichever interval finishes earliest, leaving the most room for everything after it — that greedy choice provably keeps the maximum number of intervals.
Track the end of the last kept interval; any interval starting before that end is an overlap that has to go.
Step-by-Step Analysis
Sort intervals by end time.
Set prev_end to the end of the first interval, and a removal count to 0.
For each following interval, if its start is before prev_end, it overlaps — increment count and keep prev_end as is (the earlier-ending interval stays kept).
Otherwise, there's no overlap — update prev_end to this interval's end.
Return count.
Complexity
Time: O(n log n) for the sort — Space: O(1) extra
Code
def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x: x[1])
count = 0
prev_end = intervals[0][1]
for start, end in intervals[1:]:
if start < prev_end:
count += 1
else:
prev_end = end
return count
Code Explanation
How the solution above works, piece by piece.
Sort by end. Among overlapping intervals, keeping the one that ends first can never hurt, because it blocks the least future time.
prev_end is the end of the last kept interval.
If the next interval starts before prev_end, it overlaps: remove it (count += 1) and keep prev_end unchanged.
Otherwise keep it and move prev_end to its end.
O(n log n) for the sort.
Visual Walkthrough
Running it on intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]:
Sorted by end time. Keeping the interval that ends earliest leaves the most room for the rest. [1, 3] starts before the previous kept end (2), so it overlaps and is removed: 1 removal.