#435 Non-overlapping Intervals
the problem
In plain words
Return the minimum number of intervals to remove so the rest don't overlap. Intervals that only touch, like [1,2] and [2,3], do not overlap.
in intervals = [[1,2],[2,3],[3,4],[1,3]]
out 1
Remove [1,3].
in intervals = [[1,2],[1,2],[1,2]]
out 2
in intervals = [[1,2],[2,3]]
out 0
They only touch.
- 1 ≤ intervals.length ≤ 10⁵
- −5·10⁴ ≤ start < end ≤ 5·10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval scheduling (sort by end)
Fewest removals = n − (most you can keep). The most you can keep is classic activity selection: sort by end, keep whatever fits.
solutions
From brute force to optimal
Sort by start. keep[i] = 1 + max keep[j] over earlier j that end by intervals[i]'s start.
- Sort by start.
- For each i, scan all j < i.
- Answer = n − max(keep).
Two nested loops. Too slow for n = 10⁵, but correct.
The keep array.
class Solution { public int eraseOverlapIntervals(int[][] intervals) { int n = intervals.length; Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); int[] keep = new int[n]; // keep[i]: most intervals kept, ending with interval i int best = 0; for (int i = 0; i < n; i++) { keep[i] = 1; for (int j = 0; j < i; j++) { if (intervals[j][1] <= intervals[i][0]) keep[i] = Math.max(keep[i], keep[j] + 1); } best = Math.max(best, keep[i]); } return n - best; }}Sort by start. On a clash, remove whichever of the two ends later, keeping the smaller end.
- Sort by start.
- If iv[0] ≥ prevEnd, keep it.
- Else removed++, prevEnd = min(prevEnd, iv[1]).
Sort + one pass.
Only what the sort needs.
class Solution { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); int removed = 0, prevEnd = Integer.MIN_VALUE; for (int[] iv : intervals) { if (iv[0] >= prevEnd) { prevEnd = iv[1]; // no clash: keep it } else { removed++; // clash: drop the one that ends later prevEnd = Math.min(prevEnd, iv[1]); } } return removed; }}Activity selection. Count how many you keep; removals = n − kept.
- Sort by end.
- Keep iv if iv[0] ≥ lastEnd, then set lastEnd = iv[1].
- Return n − kept.
Sort + one pass.
Only what the sort needs.
class Solution { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // earliest END first int kept = 0, lastEnd = Integer.MIN_VALUE; for (int[] iv : intervals) { if (iv[0] < lastEnd) continue; // clashes with the last kept one: remove it kept++; lastEnd = iv[1]; } return intervals.length - kept; }}Dry run (grey bars are the removals)
in the room
How to say it in the interview
talk track
- Flip the question: "minimum removals" = n − "maximum kept".
- Exchange argument: the earliest-ending interval can replace the first interval of any optimal set without causing a clash.
traps
- Treating touching ends as overlap (
<=) gives a wrong count for [[1,2],[2,3]].
what they ask next
Follow-ups
Return which intervals to remove?
Record the indices you skip in the greedy pass. You'll need the original indices, so sort an index array.
before you submit
Edge cases to test
- Touching [1,2] and [2,3] → 0 removals.
- Identical copies [[1,2],[1,2],[1,2]] → 2.
- One long interval over many short ones → remove just the long one.
- Negative coordinates are allowed; the comparator must not care.
practise next
Similar problems
- #452Minimum Number of Arrows to Burst BalloonsMediumin Intervals
- #252Meeting RoomsEasyin IntervalsLeetCode Premium
- #300Longest Increasing SubsequenceMediumin Dynamic Programming