Non-overlapping Intervals
Medium· Sorting· Activity Selection
Problem
Return the minimum number of intervals you must remove so that the rest do not overlap. Intervals that only touch at an endpoint, like [1,2] and [2,3], do not overlap.
Examples
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Remove [1,3] and the rest are disjoint.
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Constraints
- • 1 <= intervals.length <= 10^5
- • -5 * 10^4 <= start < end <= 5 * 10^4
Hints & approach
Hint 1
Minimizing removals is the same as maximizing how many intervals you keep.
Hint 2
This is the classic activity-selection problem.
Hint 3
Always keep the interval that finishes earliest; it leaves the most room for the rest.
Approachtry the hints first
Sort intervals by end. Keep the end of the last kept interval, starting at negative infinity. For each interval, if its start is at least that end, keep it and update the end; otherwise it conflicts and is removed. Choosing the earliest finishing interval is optimal by an exchange argument. Return the total minus the number kept.
Time O(n log n) · Space O(1)