Non-overlapping Intervals (LC 435): Greedy by End Time

Find the fewest intervals to delete so the rest do not overlap. Sort by end time and greedily keep each interval that starts after the last kept one ends. O(n log n) time, O(1) extra space beyond sorting.

Language Selection

Choose your preferred programming language

Showing: Python

Non-overlapping Intervals

Problem Statement

You are given an array intervals, where each element [start, end] describes a half-open range of time with start < end. Two intervals overlap only if they share more than a single point, so [1, 3] and [3, 5] do not overlap, but [1, 3] and [2, 5] do.

Return the smallest number of intervals you must delete so that no two of the remaining intervals overlap.

Examples

Example 1:

Input: intervals = [[1,3],[2,5],[4,6],[6,8]]
Output: 1
Explanation: Deleting [2,5] leaves [1,3],[4,6],[6,8]. [4,6] and [6,8] only touch, which is allowed.

Example 2:

Input: intervals = [[0,10],[1,2],[3,4],[5,6]]
Output: 1
Explanation: The long interval [0,10] overlaps all the others. Deleting it alone is enough.

Example 3:

Input: intervals = [[2,3],[2,3],[2,3]]
Output: 2
Explanation: Identical intervals overlap each other, so only one copy can stay.

Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start_i < end_i <= 5 * 10^4

Approach 1: Dynamic Programming on Sorted Starts

Algorithm

Deleting as few intervals as possible is the same as keeping as many as possible. So find the largest set of pairwise non-overlapping intervals, then subtract its size from n.

Sort by start time. In any valid kept set, listed in this order, each interval ends no later than the next one starts. Let dp[i] be the size of the largest valid set whose last interval is i:

  • dp[i] = 1 + max(dp[j]) over all j < i with end_j <= start_i, or 1 if there is no such j.

The best kept set is max(dp), and the answer is n - max(dp).

  1. Sort the intervals by start.
  2. For each i, scan every earlier j and apply the recurrence.
  3. Return n - max(dp).

This is the same shape as Longest Increasing Subsequence. It is correct, but O(n^2) is too slow for n = 10^5; it is mainly useful for explaining why the greedy works.

Implementation

Python:

from typing import List


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        ivs = sorted(intervals)
        n = len(ivs)
        dp = [1] * n  # dp[i]: most intervals we can keep, ending with ivs[i]
        for i in range(n):
            for j in range(i):
                if ivs[j][1] <= ivs[i][0]:  # j finishes before i starts
                    dp[i] = max(dp[i], dp[j] + 1)
        return n - max(dp)

Java:

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int n = intervals.length;
        int[] dp = new int[n]; // dp[i]: most intervals we can keep, ending with i
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) { // j finishes before i starts
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return n - best;
    }
}

Go:

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(a, b int) bool { return intervals[a][0] < intervals[b][0] })
    n := len(intervals)
    dp := make([]int, n) // dp[i]: most intervals we can keep, ending with i
    best := 0
    for i := 0; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if intervals[j][1] <= intervals[i][0] { // j finishes before i starts
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        best = max(best, dp[i])
    }
    return n - best
}

JavaScript:

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const n = intervals.length;
    const dp = new Array(n).fill(1); // dp[i]: most intervals we can keep, ending with i
    let best = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (intervals[j][1] <= intervals[i][0]) { // j finishes before i starts
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        best = Math.max(best, dp[i]);
    }
    return n - best;
};

C#:

using System;

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        int n = intervals.Length;
        var dp = new int[n]; // dp[i]: most intervals we can keep, ending with i
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) { // j finishes before i starts
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
            best = Math.Max(best, dp[i]);
        }
        return n - best;
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
        int n = static_cast<int>(intervals.size());
        vector<int> dp(n, 1); // dp[i]: most intervals we can keep, ending with i
        int best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) { // j finishes before i starts
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            best = max(best, dp[i]);
        }
        return n - best;
    }
};

Complexity Analysis

  • Time: O(n^2) for the double loop. The sort adds O(n log n).
  • Space: O(n) for the dp array (the Python version also makes a sorted copy).

Approach 2: Greedy by Earliest End (Optimal)

Algorithm

This is the classic interval scheduling problem. To keep the most intervals, always keep the one that finishes first. Finishing early leaves the most room for everything after it.

Why it is safe: suppose some optimal solution keeps a different first interval X. The earliest-ending interval E ends no later than X, so replacing X with E cannot create an overlap with the rest of that solution. Repeating this argument interval by interval shows the greedy set is as large as any optimal set.

  1. Sort the intervals by end time.
  2. Keep the first interval and remember its end as prevEnd.
  3. For each next interval:
    • If its start is >= prevEnd, it does not overlap. Keep it and set prevEnd to its end.
    • Otherwise it overlaps the last kept interval. Delete it (count it) and leave prevEnd unchanged, since the kept interval ends earlier.
  4. Return the delete count.

Implementation

Python:

from typing import List


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda iv: iv[1])  # earliest end first
        removed = 0
        prev_end = intervals[0][1]
        for start, end in intervals[1:]:
            if start >= prev_end:
                prev_end = end   # no overlap: keep it
            else:
                removed += 1     # overlaps the last kept interval: drop it
        return removed

Java:

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // earliest end first
        int removed = 0;
        int prevEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= prevEnd) {
                prevEnd = intervals[i][1]; // no overlap: keep it
            } else {
                removed++;                 // overlaps the last kept interval: drop it
            }
        }
        return removed;
    }
}

Go:

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    // Earliest end first
    sort.Slice(intervals, func(a, b int) bool { return intervals[a][1] < intervals[b][1] })
    removed := 0
    prevEnd := intervals[0][1]
    for _, iv := range intervals[1:] {
        if iv[0] >= prevEnd {
            prevEnd = iv[1] // no overlap: keep it
        } else {
            removed++ // overlaps the last kept interval: drop it
        }
    }
    return removed
}

JavaScript:

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[1] - b[1]); // earliest end first
    let removed = 0;
    let prevEnd = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= prevEnd) {
            prevEnd = intervals[i][1]; // no overlap: keep it
        } else {
            removed++;                 // overlaps the last kept interval: drop it
        }
    }
    return removed;
};

C#:

using System;

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1])); // earliest end first
        int removed = 0;
        int prevEnd = intervals[0][1];
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] >= prevEnd) {
                prevEnd = intervals[i][1]; // no overlap: keep it
            } else {
                removed++;                 // overlaps the last kept interval: drop it
            }
        }
        return removed;
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // Earliest end first
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
        int removed = 0;
        int prevEnd = intervals[0][1];
        for (size_t i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= prevEnd) {
                prevEnd = intervals[i][1]; // no overlap: keep it
            } else {
                removed++;                 // overlaps the last kept interval: drop it
            }
        }
        return removed;
    }
};

Complexity Analysis

  • Time: O(n log n) for the sort. The scan is O(n).
  • Space: O(1) extra besides the sort’s own working memory (for example O(log n) stack for C++ std::sort, O(n) for Python’s Timsort and Java’s object sort). The Python slice intervals[1:] also copies n - 1 references; iterate by index if you need to avoid that.

Key Insights

  1. Flip the question: minimum deletions = n minus the maximum number of non-overlapping intervals you can keep.
  2. Sort by end, not start: the interval that ends first is always a safe choice to keep. Sorting by start and keeping the earliest start can choose one long interval that blocks many short ones.
  3. Touching is fine: use start >= prevEnd for “no overlap”. With >, [1,3] and [3,5] would wrongly count as overlapping.
  4. On a conflict, drop the later-ending interval: after sorting by end, the current interval always ends at or after the kept one, so deleting it keeps prevEnd as small as possible.

Edge Cases

  1. Single interval: nothing to delete, answer 0.
  2. Chain of touching intervals: [[2,3],[3,4],[4,5]] needs 0 deletions.
  3. All identical: n copies of [2,3] need n - 1 deletions.
  4. One interval covering all others: [[0,10],[1,2],[3,4],[5,6]] needs 1 deletion (the long one).
  5. Negative coordinates: [[-5,-1],[-3,2],[1,4]] needs 1 deletion. Comparisons work the same for negative values, and differences in sort comparators stay within int range for these bounds.

Common Mistakes

  1. Sorting by start and greedily keeping: without extra logic this fails on [[1,100],[2,3],[4,5]], where keeping [1,100] forces two deletions instead of one.
  2. Treating touching intervals as overlapping: use >=, not >.
  3. Updating prevEnd on a deletion: when an interval is dropped, the last kept interval has not changed.
  4. Comparator overflow habits: a[1] - b[1] is safe within these bounds, but Integer.compare (or CompareTo) is the safer habit for wider ranges.
  5. Counting kept intervals and returning that: the problem asks for the number removed.

Interview Tips

  1. Name the pattern: say “this is interval scheduling: keep the most non-overlapping intervals by earliest finish time”.
  2. Give the exchange argument in one or two sentences: swapping any first choice for the earliest-ending interval never hurts.
  3. Mention the DP as a stepping stone: it shows you can find a correct answer first and then improve it.
  4. Test a counterexample for sort-by-start: [[1,100],[2,3],[4,5]] shows why the sort key matters.

Follow-up Questions

  1. Return which intervals to delete? Record the indices you skip during the greedy scan (sort index pairs instead of raw intervals).
  2. Weighted version (maximize kept weight)? Greedy no longer works. Sort by end and use DP with binary search for the last compatible interval, O(n log n) (weighted interval scheduling, LC 1235).
  3. Minimum arrows to burst balloons (LC 452)? The same greedy by end, except touching intervals do count as overlapping there.
  4. Closed intervals where touching counts as overlap? Change the keep test to start > prevEnd.