Intervals & Greedy · 045Medium
Non-overlapping Intervals
Given an array of intervals, return the minimum number you must remove so that the rest are non-overlapping.
Constraints
- 1 <= intervals.length <= 10^5
- intervals[i].length == 2, -5 * 10^4 <= start < end <= 5 * 10^4
Examples
eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]) -> 1 eraseOverlapIntervals([[1,2],[1,2],[1,2]]) -> 2 eraseOverlapIntervals([[1,2],[2,3]]) -> 0 // touching is fine eraseOverlapIntervals([[1,2]]) -> 0 // a single interval never overlaps eraseOverlapIntervals([[-5,-1],[-3,2],[0,4]]) -> 1 // negative bounds are allowed eraseOverlapIntervals([[1,10],[2,3],[3,4],[4,5]]) -> 1 // drop the one long interval
Edge cases
- Intervals that only touch at an endpoint do not overlap.
- Identical duplicate intervals.
Show the target complexity (spoiler)
- Naive
- O(2^n) time — try every subset and keep the largest compatible one.
- Target
- O(n log n) time — sort by END, then greedily keep every interval starting at or after the last kept end.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/11-intervals-greedy/045-non-overlapping-intervals.js ./practice c 045