#435 - Non-overlapping Intervals

MediumIntervals

Given an array of intervals intervals[i] = [start, end], return the minimum number of intervals you need to remove to make the rest non-overlapping.

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

Solution Space

Try it

/**
 * Returns the minimum number of intervals to remove for non-overlapping.
 * Greedy: sort by end time, always keep the interval that ends earliest.
 *
 * @param intervals Array of [start, end] intervals
 * @returns Minimum removals
 */
export function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);

  let kept = 0;
  let prevEnd = -Infinity;

  for (const [start, end] of intervals) {
    if (start >= prevEnd) {
      kept++;
      prevEnd = end;
    }
  }

  return intervals.length - kept;
}

Approach: greedy by end time – sort intervals by end time. Greedily keep each interval whose start >= previous end. The answer is `total - kept`.

Time: O(n log n) – sorting dominates.

Space: O(1) extra – sorting in place.

#1268 Search Suggestions System

#452 Minimum Number of Arrows to Burst Balloons