Given a list of intervals, the machine must remove the fewest possible so that no two remaining intervals overlap. This is interval scheduling in reverse: maximize the number of intervals kept, then subtract from the total.
The key insight is that keeping the interval that ends earliest is always safe. An interval that finishes sooner leaves more room for everything after it, so no optimal solution is ever worse for having chosen it. This makes the greedy choice globally correct, not just locally plausible.
The approach runs in three steps. First, sort the intervals by end time. Second, walk the sorted list, keeping the first interval and setting its end as the current boundary. Third, for each later interval, keep it if its start is at or after the boundary — intervals that touch at a point do not overlap — otherwise count it as a removal and leave the boundary untouched. Time is O(n log n) from the sort and space is O(1).
The trickiest edge case is touching endpoints: [1,2] and [2,3] do not overlap because the end is exclusive in the overlap check, so the machine must use start >= last_end to keep both. Mistaking this for start > last_end inflates the removal count by one.
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1])
count, last_end = 0, float("-inf")
for start, end in intervals:
if start >= last_end:
last_end = end
else:
count += 1
return count