medium

Non-overlapping Intervals

Find the fewest intervals to remove so none of the remaining intervals overlap.

1. Define the problem

Non-overlapping Intervals

Given an array of intervals where intervalsi = [start_i, end_i], return the minimum number of intervals you need to remove so the rest do not overlap. Sort the intervals by their end time , then sweep once, keeping any interval that starts at or after the end of the last interval you kept. Whatever is not kept must be removed.

Constraints

  • 1 ≤ intervals.length ≤ 105
  • intervalsi.length == 2
  • -5 × 104 ≤ start_i < end_i ≤ 5 × 104

Example

Inputintervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output1

Explanation Removing [1, 3] leaves [1, 2], [2, 3], [3, 4], which do not overlap.

2. Know the words first

In plain terms

Interval
A range with a start and an end, like [1, 3] meaning "from 1 to 3".
3. Visualize the solution

Sweep intervals sorted by end time, keeping what fits

Sweep intervals sorted by end time, keeping what fits
StatuslastEnd=2

Sorted by end: [1,2] is kept first. lastEnd becomes 2, kept=1.

What happens in this step

sorted (by end): [1,2], [2,3], [1,3], [3,4]

lastEnd = sorted[0][1] = 2, kept = 1

The first interval after sorting is always kept — it seeds the running lastEnd.
Step 1 of 5

Steps to visualize

  1. Sort the intervals by their end value.
  2. Keep the first interval and remember its end as lastEnd.
  3. For each following interval, keep it only if its start is at or after lastEnd, and update lastEnd.
  4. Any interval that overlaps the last one kept must be removed.
  5. The answer is the total count minus how many were kept.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sweep intervals sorted by end time, keeping what fits
StatuslastEnd=2

Sorted by end: [1,2] is kept first. lastEnd becomes 2, kept=1.

What happens in this step

sorted (by end): [1,2], [2,3], [1,3], [3,4]

lastEnd = sorted[0][1] = 2, kept = 1

The first interval after sorting is always kept — it seeds the running lastEnd.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

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

  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    if (start >= lastEnd) {
      kept++;
      lastEnd = end;
    }
  }

  return intervals.length - kept;
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]1example from the docstring
intervals = [[1, 2], [1, 2], [1, 2]]2every interval is identical, only one can be kept
intervals = [[1, 2], [2, 3]]0touching but not overlapping intervals, nothing to remove
intervals = [[1, 2]]0smallest valid input, a single interval
intervals = [[1, 10], [2, 3], [4, 5], [6, 7]]1one large interval overlapping several small ones
intervals = [[1, 2], [3, 4], [5, 6]]0a larger set with no overlaps at all

Keep reading