non-overlapping-intervals.ts

/**
 * 435. Non-overlapping Intervals  (Medium)
 * Link: https://leetcode.com/problems/non-overlapping-intervals/
 *
 * Return the minimum number of intervals to remove so that the rest are
 * non-overlapping.
 *
 * Example:
 *   Input:  [[1,2],[2,3],[3,4],[1,3]]
 *   Output: 1            // remove [1,3]
 *
 * Approach:
 *   Greedy by earliest end time. Sort by end; always keep the interval that
 *   finishes first, since it leaves the most room. Walk through: if the next
 *   interval starts before the last kept one ends, it overlaps and must be
 *   removed; otherwise keep it and advance the boundary.
 *
 * Time:  O(n log n)  — the sort dominates.
 * Space: O(1)
 */
export function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length === 0) return 0;

  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let removed = 0;
  let prevEnd = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] < prevEnd) {
      removed++; // overlap -> drop this one
    } else {
      prevEnd = sorted[i][1];
    }
  }

  return removed;
}