#65 · Intervals

Non-overlapping Intervals

Given a list of intervals, return the minimum number of intervals to remove so that the remaining ones do not overlap. Intervals that only touch (one ends where the next starts) do not overlap.

MediumLeetCode

Being examined
New / inserted
Kept / merged / answer
Removed / conflict
Untouched

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Activity selection (greedy by earliest end)

Removing the fewest intervals is the same as keeping the most. Among compatible choices, the interval that ends first leaves the most room, so always keep it. After sorting by end time, one pass keeps an interval whenever it starts no earlier than the last kept end.

Memory layout

A sorted array and two numbers (last end, count).

Operation	Cost
time	O(n log n)
space	O(1) beyond the sort

Longest chain DP

dp[i] = the most intervals that can be kept if interval i is the last one, found by checking every earlier compatible interval. It is the interval version of the longest increasing subsequence and is O(n²).

Memory layout

One integer per interval.

Operation	Cost
time / space	O(n²) / O(n)

Why it fits

Keeping the maximum number of mutually compatible intervals is the classic interval scheduling problem, and its greedy solution (earliest finish first) is provably optimal.
An exchange argument shows it: any optimal solution can swap its first interval for the one that ends earliest without creating a conflict.
Sorting by start and dropping the later-ending interval on a conflict is the same greedy in disguise: it keeps the smaller prevEnd.

Why alternatives degrade

Greedy by earliest start:: A long interval that starts first can block many short ones: [1,100] would be kept while [2,3], [4,5], [6,7] are all removed.
Greedy by shortest length:: A short interval in the middle can overlap two long ones that would otherwise both be kept, giving a worse answer.
Trying all subsets:: There are 2ⁿ subsets, and checking each is O(n).

Four approaches, from naive to production

1 · beginner

Recursion: keep it or skip it

time O(2ⁿ)space O(n)

Sort by start. For each interval, either skip it or keep it if it does not overlap the last kept one, and take the better outcome. The answer is the total count minus the most that can be kept.

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    function<int(int, int)> keep = [&](int i, int lastEnd) -> int {
        if (i == (int)sorted.size()) return 0;
        int best = keep(i + 1, lastEnd);
        if (sorted[i][0] >= lastEnd) best = max(best, 1 + keep(i + 1, sorted[i][1]));
        return best;
    };
    return (int)sorted.size() - keep(0, -1000000000);
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    return sorted.length - keep(sorted, 0, -1000000000);
}
private int keep(int[][] sorted, int i, int lastEnd) {
    if (i == sorted.length) return 0;
    int best = keep(sorted, i + 1, lastEnd);
    if (sorted[i][0] >= lastEnd) best = Math.max(best, 1 + keep(sorted, i + 1, sorted[i][1]));
    return best;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    def keep(i, last_end):
        if i == len(sorted_iv): return 0
        best = keep(i + 1, last_end)
        if sorted_iv[i][0] >= last_end: best = max(best, 1 + keep(i + 1, sorted_iv[i][1]))
        return best
    return len(sorted_iv) - keep(0, -10**9)

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const keep = (i: number, lastEnd: number): number => {
    if (i === sorted.length) return 0;
    let best = keep(i + 1, lastEnd);
    if (sorted[i][0] >= lastEnd) best = Math.max(best, 1 + keep(i + 1, sorted[i][1]));
    return best;
  };
  return sorted.length - keep(0, -1e9);
}

Flaws & bottlenecks

Two branches per interval gives an exponential number of calls.
The same (position, last end) state can be reached through different choices and is recomputed.
Recursion depth is n.

Interviewer cross-questions

What is the state of the recursion?

Say: The position i and the end of the last kept interval. With memoisation there are at most n² such states, which leads to the DP version.

Why is skipping always allowed?

Say: Removing an interval can never create an overlap, so the "skip" branch is always valid.

Why count removals as n minus the kept count?

Say: Every interval is either kept or removed, so minimising removals is maximising kept intervals.

2 · intermediate

DP: longest chain of compatible intervals

time O(n²)space O(n)

Sort by start. dp[i] is the longest chain of compatible intervals that ends with interval i: one more than the best dp[j] over earlier intervals j that end no later than i starts.

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    int n = sorted.size();
    vector<int> dp(n, 1);
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (sorted[j][1] <= sorted[i][0]) dp[i] = max(dp[i], dp[j] + 1);
        }
        best = max(best, dp[i]);
    }
    return n - best;
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    int n = sorted.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (sorted[j][1] <= sorted[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return n - best;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    n = len(sorted_iv)
    dp = [1] * n
    best = 1
    for i in range(1, n):
        for j in range(i):
            if sorted_iv[j][1] <= sorted_iv[i][0]: dp[i] = max(dp[i], dp[j] + 1)
        best = max(best, dp[i])
    return n - best

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const n = sorted.length;
  const dp = new Array<number>(n).fill(1);
  let best = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (sorted[j][1] <= sorted[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return n - best;
}

Flaws & bottlenecks

Quadratic: too slow for 100,000 intervals.
Two nested loops over mostly irrelevant pairs.
Needs the sort by start for the dependency order.

Interviewer cross-questions

How does this relate to the longest increasing subsequence?

Say: It is the same shape: dp[i] depends on earlier items that are "compatible" with i. With an end-sorted order, the binary-search trick would give O(n log n), but the greedy argument gives it more simply.

Why sort by start?

Say: Then every compatible predecessor of i has a smaller index, so dp can be filled left to right.

What is the answer from dp?

Say: n minus the largest dp value: all other intervals are removed.

3 · advanced

Greedy: earliest end first

time O(n log n)space O(1) beyond the sort

Sort by end time. Keep the first interval, then keep each later interval whose start is no earlier than the last kept end. The number removed is n minus the number kept.

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    int kept = 1;
    int end = sorted[0][1];
    for (int i = 1; i < (int)sorted.size(); i++) {
        if (sorted[i][0] >= end) {
            kept++;
            end = sorted[i][1];
        }
    }
    return (int)sorted.size() - kept;
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));
    int kept = 1;
    int end = sorted[0][1];
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] >= end) {
            kept++;
            end = sorted[i][1];
        }
    }
    return sorted.length - kept;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[1])
    kept = 1
    end = sorted_iv[0][1]
    for i in range(1, len(sorted_iv)):
        if sorted_iv[i][0] >= end:
            kept += 1
            end = sorted_iv[i][1]
    return len(sorted_iv) - kept

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let kept = 1;
  let end = sorted[0][1];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= end) {
      kept++;
      end = sorted[i][1];
    }
  }
  return sorted.length - kept;
}

Flaws & bottlenecks

The correctness proof (exchange argument) is less obvious than the DP.
Must sort by END, not start (a common mistake).
Ties in end time need no special handling, but touching intervals must be allowed (>= not >).

Interviewer cross-questions

Why does keeping the earliest-ending interval never hurt?

Say: Take any optimal solution. Replace its first interval by the earliest-ending one: it ends no later, so it cannot overlap anything the original did not. The count stays the same, so keeping it is safe.

Why >= and not >?

Say: The problem treats intervals that only touch ([1,2] and [2,3]) as non-overlapping, so a start equal to the last end is allowed.

What if intervals have weights?

Say: Then greedy fails and you need weighted interval scheduling: sort by end and use DP with binary search for the latest compatible interval.

4 · expert

Greedy by start, keep the earlier end

time O(n log n)space O(1) beyond the sort

Sort by start and remember only the end of the interval currently kept. When the next interval overlaps it, count one removal and keep whichever ends earlier (prevEnd = min); otherwise it becomes the new kept interval.

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    int prevEnd = sorted[0][1];
    int removed = 0;
    for (int i = 1; i < (int)sorted.size(); i++) {
        if (sorted[i][0] < prevEnd) {
            removed++;
            prevEnd = min(prevEnd, sorted[i][1]);
        } else {
            prevEnd = sorted[i][1];
        }
    }
    return removed;
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
    int prevEnd = sorted[0][1];
    int removed = 0;
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] < prevEnd) {
            removed++;
            prevEnd = Math.min(prevEnd, sorted[i][1]);
        } else {
            prevEnd = sorted[i][1];
        }
    }
    return removed;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    prev_end = sorted_iv[0][1]
    removed = 0
    for i in range(1, len(sorted_iv)):
        if sorted_iv[i][0] < prev_end:
            removed += 1
            prev_end = min(prev_end, sorted_iv[i][1])
        else:
            prev_end = sorted_iv[i][1]
    return removed

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  let prevEnd = sorted[0][1];
  let removed = 0;
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] < prevEnd) {
      removed++;
      prevEnd = Math.min(prevEnd, sorted[i][1]);
    } else {
      prevEnd = sorted[i][1];
    }
  }
  return removed;
}

Flaws & bottlenecks

It never records which intervals were removed, only how many.
The "keep the earlier end" step is subtle: the removed interval is not necessarily the one just read.
Sorting by start with ties in arbitrary order still works but is harder to argue about.

Interviewer cross-questions

Is this really the same as the end-sorted greedy?

Say: Yes. On a conflict you drop the interval that ends later, which is exactly what the earliest-end rule would have preferred. It lets you sort by start, the same order other interval problems (merging) use.

Why use min on the conflict?

Say: Keeping the interval with the smaller end leaves the most room for the intervals still to come.

How would you also return the removed intervals?

Say: On a conflict, record the one with the larger end as removed. That needs the intervals themselves, not just the end value.

Synchronized code walkthrough

Showing: Recursion: keep it or skip it — shares the player above; click any step to jump.

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    function<int(int, int)> keep = [&](int i, int lastEnd) -> int {
        if (i == (int)sorted.size()) return 0;
        int best = keep(i + 1, lastEnd);
        if (sorted[i][0] >= lastEnd) best = max(best, 1 + keep(i + 1, sorted[i][1]));
        return best;
    };
    return (int)sorted.size() - keep(0, -1000000000);
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    return sorted.length - keep(sorted, 0, -1000000000);
}
private int keep(int[][] sorted, int i, int lastEnd) {
    if (i == sorted.length) return 0;
    int best = keep(sorted, i + 1, lastEnd);
    if (sorted[i][0] >= lastEnd) best = Math.max(best, 1 + keep(sorted, i + 1, sorted[i][1]));
    return best;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    def keep(i, last_end):
        if i == len(sorted_iv): return 0
        best = keep(i + 1, last_end)
        if sorted_iv[i][0] >= last_end: best = max(best, 1 + keep(i + 1, sorted_iv[i][1]))
        return best
    return len(sorted_iv) - keep(0, -10**9)

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const keep = (i: number, lastEnd: number): number => {
    if (i === sorted.length) return 0;
    let best = keep(i + 1, lastEnd);
    if (sorted[i][0] >= lastEnd) best = Math.max(best, 1 + keep(i + 1, sorted[i][1]));
    return best;
  };
  return sorted.length - keep(0, -1e9);
}

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    int n = sorted.size();
    vector<int> dp(n, 1);
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (sorted[j][1] <= sorted[i][0]) dp[i] = max(dp[i], dp[j] + 1);
        }
        best = max(best, dp[i]);
    }
    return n - best;
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    int n = sorted.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (sorted[j][1] <= sorted[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return n - best;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    n = len(sorted_iv)
    dp = [1] * n
    best = 1
    for i in range(1, n):
        for j in range(i):
            if sorted_iv[j][1] <= sorted_iv[i][0]: dp[i] = max(dp[i], dp[j] + 1)
        best = max(best, dp[i])
    return n - best

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const n = sorted.length;
  const dp = new Array<number>(n).fill(1);
  let best = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (sorted[j][1] <= sorted[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return n - best;
}

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    int kept = 1;
    int end = sorted[0][1];
    for (int i = 1; i < (int)sorted.size(); i++) {
        if (sorted[i][0] >= end) {
            kept++;
            end = sorted[i][1];
        }
    }
    return (int)sorted.size() - kept;
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));
    int kept = 1;
    int end = sorted[0][1];
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] >= end) {
            kept++;
            end = sorted[i][1];
        }
    }
    return sorted.length - kept;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[1])
    kept = 1
    end = sorted_iv[0][1]
    for i in range(1, len(sorted_iv)):
        if sorted_iv[i][0] >= end:
            kept += 1
            end = sorted_iv[i][1]
    return len(sorted_iv) - kept

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let kept = 1;
  let end = sorted[0][1];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= end) {
      kept++;
      end = sorted[i][1];
    }
  }
  return sorted.length - kept;
}

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    int prevEnd = sorted[0][1];
    int removed = 0;
    for (int i = 1; i < (int)sorted.size(); i++) {
        if (sorted[i][0] < prevEnd) {
            removed++;
            prevEnd = min(prevEnd, sorted[i][1]);
        } else {
            prevEnd = sorted[i][1];
        }
    }
    return removed;
}

public int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
    int prevEnd = sorted[0][1];
    int removed = 0;
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] < prevEnd) {
            removed++;
            prevEnd = Math.min(prevEnd, sorted[i][1]);
        } else {
            prevEnd = sorted[i][1];
        }
    }
    return removed;
}

def erase_overlap_intervals(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    prev_end = sorted_iv[0][1]
    removed = 0
    for i in range(1, len(sorted_iv)):
        if sorted_iv[i][0] < prev_end:
            removed += 1
            prev_end = min(prev_end, sorted_iv[i][1])
        else:
            prev_end = sorted_iv[i][1]
    return removed

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  let prevEnd = sorted[0][1];
  let removed = 0;
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] < prevEnd) {
      removed++;
      prevEnd = Math.min(prevEnd, sorted[i][1]);
    } else {
      prevEnd = sorted[i][1];
    }
  }
  return removed;
}