Medium · Earliest Finish Time
Understand → Visualise → Practice.
Return the minimum intervals to remove so the remaining half-open intervals do not overlap.
To keep as many intervals as possible, always keep the one that finishes first; it leaves the most room for the rest. Removals = total − kept.
Order intervals by their end point.
Keep an interval if its start is at or after the last kept end, then update that end.
Return the number of intervals minus the number kept.
O(n log n) time and O(1) extra space.
Intervals are half-open, so [1, 2] and [2, 3] touch but do not overlap; use start ≥ end.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.