LeetCode 435 · Medium · Intervals

Non-overlapping Intervals

Return the fewest intervals you must delete so that the rest do not overlap. Intervals that only touch, like [1,2] and [2,3], do not count as overlapping.

O(n log n)time · the sort
O(1)extra space
greedykeep the earlier end

1–10 intervals · [start,end] with 0 ≤ start < end ≤ 20 · any order

Number line sorted by start · green: kept · dashed: removed · the line marks prevEnd

public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); int res = 0; int prevEnd = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { int start = intervals[i][0]; int end = intervals[i][1]; if (start >= prevEnd) { // no overlap prevEnd = end; } else { // overlap: drop the one that ends later res++; prevEnd = Math.min(end, prevEnd); } } return res;}
[start, end]
—
prevEnd
—
res
0

Why it works

  1. Brute force tries every subset of intervals to keep and checks it for overlaps: O(2ⁿ · n). Removing the fewest is the same as keeping the most.
  2. Greedy: when two intervals clash, keep the one that ends first. It leaves the most room for everything to its right, so no optimal answer is ever hurt by that choice. prevEnd is the end of the last interval you kept.
  3. Cost: the sort is O(n log n); the sweep is one comparison per interval, O(n), with O(1) extra space.
  4. Pitfall: on overlap, do not blindly keep the earlier interval. prevEnd = Math.min(end, prevEnd) swaps in the new one when it ends sooner, like [2,4] replacing [1,20]. And use ≥: touching intervals are fine.
  5. Related: this is the activity-selection problem. Minimum Number of Arrows to Burst Balloons (452) is the same sweep with closed ends.