Non-overlapping Intervals
Medium · Intervals · Array · Greedy · Sorting
Problem
Given a list of [start, end] intervals, return the fewest you must remove so that none of the rest overlap.
Intervals that merely touch — one ending exactly where another begins — do not count as overlapping.
Examples
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1
Removing [1,3] leaves three that only touch.
Input: intervals = [[1,2],[1,2],[1,2]] Output: 2
Two of the three identical intervals must go.
Input: intervals = [[1,2],[2,3]] Output: 0
Touching is allowed.
Constraints
- 1 <= len(intervals) <= 10^5
- -5 * 10^4 <= start < end <= 5 * 10^4
Approaches
- Sort by start, drop the longer one — time O(n log n), space O(1) extra
Related problems
Start free on Cariara · Coding problems · System design studio
