Non-overlapping Intervals

The key idea

Sort by end time, then greedily keep every interval whose start is at least the last kept interval's end. Always keeping the interval that finishes earliest leaves the most room for the ones after it, so the count of intervals you skip is the minimum number of removals.

Problem

You are given an array intervals where intervals[i] = [start_i, end_i]. Return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1,2] and [2,3] are non-overlapping.

Constraints

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= start_i < end_i <= 5 * 10^4

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1

Input: intervals = [[1,2],[1,2],[1,2]] Output: 2

Input: intervals = [[1,2],[2,3]] Output: 0

Complexity

Time: O(n log n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →