What is the brute force approach and complexity for Non-overlapping Intervals?

Try keeping or removing each interval, and take the largest set without overlaps with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Non-overlapping Intervals?

Sort by end; keep an interval when it starts at or after the last kept end with optimal time complexity O(N log N) and space complexity O(1).

How do you identify the pattern for Non-overlapping Intervals?

Look for key signals in the prompt: "remove the minimum number of intervals" indicates Flip it: keep the maximum number of intervals that don't overlap.; "non-overlapping" indicates Kept intervals form a chain in time. Only the end of the last kept one matters.; "touching is allowed" indicates The test is `start ≥ lastEnd`, with `≥`, not `>`..

Non-overlapping Intervals

Medium·LeetCode #435Basic Anchor

LeetCode

Jump:

30-Second Mental ModelIntervals (coverage / removal) — greedy by end time

Complexity:O(2^N)→O(N log N)

Key Insight

Sort by end. Walk through the list with lastEnd = end of the last kept interval. If the next interval starts at or after lastEnd, keep it and move lastEnd to its end. Otherwise it overlaps the last kept one, so remove it. Answer = n − kept.

Core Validity Invariant

An interval can be kept only if it starts at or after the end of the last kept one: start ≥ lastEnd. Touching (start == lastEnd) is fine.

Problem

You get a list of intervals, each written as [start, end].

Remove as few intervals as possible so that the ones left do not overlap each other. Return how many you removed.

Two intervals that only touch at one point, like [1, 2] and [2, 3], do not count as overlapping.

Input

An array intervals where intervals[i] = [start_i, end_i].

Output

One integer: the minimum number of intervals to remove.

Example 1

Input: intervals = [[1,2], [2,3], [3,4], [1,3]]

Output: 1

Remove [1,3]. The rest, [1,2], [2,3], [3,4], only touch each other.

Example 2

Input: intervals = [[1,2], [1,2], [1,2]]

Output: 2

All three are the same interval, so only one of them can stay.

Example 3

Input: intervals = [[1,2], [2,3]]

Output: 0

They only touch at 2, so they already don't overlap.

Constraints

• 1 ≤ intervals.length ≤ 10^5
• intervals[i].length == 2
• −5 · 10^4 ≤ start_i < end_i ≤ 5 · 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Removing the fewest is the same as keeping the most. Which of the two is easier to think about?
2.
If two intervals overlap, at least one of them has to go. Which one would you rather keep?
3.
Does a long interval help you or hurt you when you want to keep many?
4.
What does it mean for the next interval if the one you kept finishes early?
5.
Is it more useful to sort by start time or by end time here?

Brute force approach

Idea

Sort by start. Go through the intervals one by one, and for each one try both choices: remove it, or keep it (allowed only if it starts at or after the end of the last one we kept). Return n − (most kept).

Thinking process

1
I want the fewest removals, which is the same as the most intervals kept.
2
I don't know which ones to keep, so I try both options for every interval.
3
If I go in order of start time, a new interval only has to be checked against the last one I kept.
4
Two choices per interval gives 2^n combinations.

Code & Implementation

brute.cpp

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // Sort by start so the intervals we keep come in time order.
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        // Fewest removals = everything minus the most we can keep.
        return n - maxKeep(intervals, 0, INT_MIN);
    }

private:
    // The most intervals we can keep from index i onward,
    // when the last interval we kept ends at lastEnd.
    int maxKeep(vector<vector<int>>& iv, int i, int lastEnd) {
        if (i == (int)iv.size()) return 0;

        // Choice 1: remove interval i.
        int best = maxKeep(iv, i + 1, lastEnd);

        // Choice 2: keep it, but only if it starts after the last kept one ends.
        // Touching (start == lastEnd) is fine.
        if (iv[i][0] >= lastEnd) {
            best = max(best, 1 + maxKeep(iv, i + 1, iv[i][1]));
        }
        return best;
    }
};

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // Sort by start so the intervals we keep come in time order.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int n = intervals.length;
        // Fewest removals = everything minus the most we can keep.
        return n - maxKeep(intervals, 0, (long) Integer.MIN_VALUE - 1);
    }

    // The most intervals we can keep from index i onward,
    // when the last interval we kept ends at lastEnd.
    private int maxKeep(int[][] iv, int i, long lastEnd) {
        if (i == iv.length) {
            return 0;
        }

        // Choice 1: remove interval i.
        int best = maxKeep(iv, i + 1, lastEnd);

        // Choice 2: keep it, but only if it starts after the last kept one ends.
        // Touching (start == lastEnd) is fine.
        if (iv[i][0] >= lastEnd) {
            best = Math.max(best, 1 + maxKeep(iv, i + 1, iv[i][1]));
        }
        return best;
    }
}

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        # Sort by start so the intervals we keep come in time order.
        intervals.sort(key=lambda x: x[0])
        n = len(intervals)

        # The most intervals we can keep from index i onward,
        # when the last interval we kept ends at last_end.
        def max_keep(i: int, last_end: float) -> int:
            if i == n:
                return 0

            # Choice 1: remove interval i.
            best = max_keep(i + 1, last_end)

            # Choice 2: keep it, but only if it starts after the last kept one ends.
            # Touching (start == last_end) is fine.
            if intervals[i][0] >= last_end:
                best = max(best, 1 + max_keep(i + 1, intervals[i][1]))
            return best

        return n - max_keep(0, -float("inf"))

export function eraseOverlapIntervals(intervals: number[][]): number {
    // Sort by start so the intervals we keep come in time order.
    intervals.sort((a, b) => a[0] - b[0]);
    const n = intervals.length;

    // The most intervals we can keep from index i onward,
    // when the last interval we kept ends at lastEnd.
    function maxKeep(i: number, lastEnd: number): number {
        if (i === n) return 0;

        // Choice 1: remove interval i.
        let best = maxKeep(i + 1, lastEnd);

        // Choice 2: keep it, but only if it starts after the last kept one ends.
        // Touching (start == lastEnd) is fine.
        if (intervals[i][0] >= lastEnd) {
            best = Math.max(best, 1 + maxKeep(i + 1, intervals[i][1]));
        }
        return best;
    }

    return n - maxKeep(0, -Infinity);
}

Complexity

Time O(2^N)Space O(N)

Every interval doubles the number of choices. Fine for 15 intervals, hopeless for 10^5. The recursion goes N levels deep.

Better approach

Why brute force is slow

Brute force explores every combination of keep / remove, so it rebuilds the same chains of kept intervals many times.

What repeated work are we doing?

The answer to "the longest chain that ends at interval j" never changes, but brute force works it out again in every branch that reaches j.

What information can we reuse?

Store it in dp[j] once. Then each new interval only looks back at the stored values.

New approach

Idea

Sort by start. Let dp[i] be the most intervals we can keep if interval i is the last one kept. Then dp[i] = 1 + max(dp[j]) over every earlier j that ends by the time i starts (end_j ≤ start_i). The best kept set is the largest dp[i].

Thinking process

1
Brute force solves the same small question again and again: "what is the most I can keep before this interval?"
2
If interval i is the last one kept, the one kept right before it must end by start_i.
3
So the best chain ending at i is 1 plus the best chain ending at any such j.
4
This is the same shape as longest increasing subsequence.

Code & Implementation

better.cpp

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());  // by start
        int n = intervals.size();

        // dp[i] = the most intervals we can keep if interval i is the LAST one kept.
        vector<int> dp(n, 1);
        int keep = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Interval j can come right before i if it ends by the time i starts.
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            keep = max(keep, dp[i]);
        }
        return n - keep;
    }
};

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // by start
        int n = intervals.length;

        // dp[i] = the most intervals we can keep if interval i is the LAST one kept.
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int keep = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Interval j can come right before i if it ends by the time i starts.
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            keep = Math.max(keep, dp[i]);
        }
        return n - keep;
    }
}

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: x[0])  # by start
        n = len(intervals)

        # dp[i] = the most intervals we can keep if interval i is the LAST one kept.
        dp = [1] * n
        keep = 0
        for i in range(n):
            for j in range(i):
                # Interval j can come right before i if it ends by the time i starts.
                if intervals[j][1] <= intervals[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
            keep = max(keep, dp[i])
        return n - keep

export function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[0] - b[0]); // by start
    const n = intervals.length;

    // dp[i] = the most intervals we can keep if interval i is the LAST one kept.
    const dp = new Int32Array(n).fill(1);
    let keep = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            // Interval j can come right before i if it ends by the time i starts.
            if (intervals[j][1] <= intervals[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        keep = Math.max(keep, dp[i]);
    }
    return n - keep;
}

Complexity

Time O(N²)Space O(N)

Each interval looks at every interval before it: about N²/2 checks. With N = 10^5 that is 5·10^9, still too slow.

Optimized approach

Idea

Start from brute force

Brute force tries every keep / remove choice, and the DP still compares each interval with every earlier one.

Find the repeated work

Out of all the earlier intervals, only one fact matters: where the kept set currently ends. If we always keep the interval that ends earliest, that end is as small as it can be, and we never need to look back.

Define the state — what variables do I need?

lastEnd: End of the last interval we decided to keep. Anything starting at or after it is free to keep.
kept: How many intervals we have kept so far.

Define validity

An interval can be kept only if it starts at or after the end of the last kept one: start ≥ lastEnd. Touching (start == lastEnd) is fine.

Define the transitions — when does each pointer move, and why is it safe?

start ≥ lastEnd

kept++; lastEnd = end

It doesn't overlap anything we kept. Because we go in order of end, it is the earliest-ending interval that still fits, which is the best one to keep next.

start < lastEnd

remove it (skip)

It overlaps the last kept interval. It also ends at or after lastEnd (we sorted by end), so it blocks at least as much time. Keeping the one we already have is never worse.

What does the current window add to the answer?

Every kept interval adds 1 to kept. Every skipped one is one removal. The answer is n − kept.

Code & Implementation

optimal.cpp

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // Sort by END: the interval that finishes first leaves the most room for the rest.
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        int kept = 0;
        int lastEnd = INT_MIN;  // end of the last interval we kept
        for (auto& iv : intervals) {
            // Starts at or after the last kept end → no overlap (touching is OK).
            if (iv[0] >= lastEnd) {
                kept++;
                lastEnd = iv[1];
            }
            // Otherwise it overlaps the last kept one, and it ends no earlier,
            // so removing it is never worse.
        }
        return (int)intervals.size() - kept;
    }
};

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // Sort by END: the interval that finishes first leaves the most room for the rest.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int kept = 0;
        int lastEnd = Integer.MIN_VALUE; // end of the last interval we kept
        for (int[] iv : intervals) {
            // Starts at or after the last kept end -> no overlap (touching is OK).
            if (iv[0] >= lastEnd) {
                kept++;
                lastEnd = iv[1];
            }
            // Otherwise it overlaps the last kept one, and it ends no earlier,
            // so removing it is never worse.
        }
        return intervals.length - kept;
    }
}

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        # Sort by END: the interval that finishes first leaves the most room for the rest.
        intervals.sort(key=lambda x: x[1])

        kept = 0
        last_end = -float("inf")  # end of the last interval we kept
        for iv in intervals:
            # Starts at or after the last kept end -> no overlap (touching is OK).
            if iv[0] >= last_end:
                kept += 1
                last_end = iv[1]
            # Otherwise it overlaps the last kept one, and it ends no earlier,
            # so removing it is never worse.
        return len(intervals) - kept

export function eraseOverlapIntervals(intervals: number[][]): number {
    // Sort by END: the interval that finishes first leaves the most room for the rest.
    intervals.sort((a, b) => a[1] - b[1]);

    let kept = 0;
    let lastEnd = -Infinity; // end of the last interval we kept
    for (const iv of intervals) {
        // Starts at or after the last kept end -> no overlap (touching is OK).
        if (iv[0] >= lastEnd) {
            kept++;
            lastEnd = iv[1];
        }
        // Otherwise it overlaps the last kept one, and it ends no earlier,
        // so removing it is never worse.
    }
    return intervals.length - kept;
}

Complexity

Time O(N log N)Space O(1)

Sorting is O(N log N). The walk is one pass. Extra space is O(1) besides the sort.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try keeping or removing each interval, and take the largest set without overlaps	O(2^N)	O(N)
Better	dp[i] = most intervals kept if interval i is the last one; check every earlier j	O(N²)	O(N)
Optimal	Sort by end; keep an interval when it starts at or after the last kept end	O(N log N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“remove the minimum number of intervals”Flip it: keep the maximum number of intervals that don't overlap.
“non-overlapping”Kept intervals form a chain in time. Only the end of the last kept one matters.
“touching is allowed”The test is `start ≥ lastEnd`, with `≥`, not `>`.

Pick the most intervals+no two overlap+sort by end, keep the earliest finisher→Intervals (coverage / removal) — greedy by end time

This is the anchor of the coverage sub-pattern. The key choice is which end to sort by. Merge Intervals sorts by start because it glues overlaps together. Here we choose what to throw away, and the interval that ends first is always the safest one to keep. Burst Balloons uses the same greedy with one change: touching balloons share an arrow, so there it's start > arrow, not start ≥ lastEnd.

Don't make this mistake

Pattern confusion: sorting by start and keeping the first one

✗ sort(intervals.begin(), intervals.end()); // by start if (iv[0] >= lastEnd) { kept++; lastEnd = iv[1]; }

✓ sort by end (a[1] < b[1]), then the same check

This looks like Merge Intervals, but it keeps whatever starts first. With [[1,10], [2,3], [4,5], [6,7]] it keeps [1,10] and removes the other 3. Sorting by end keeps 3 and removes only [1,10]. (If you do sort by start, you must also keep the one with the smaller end when two overlap.)

Treating touching intervals as overlapping

✗ if (iv[0] > lastEnd) { ... }

✓ if (iv[0] >= lastEnd) { ... }

[1,2] and [2,3] do not overlap in this problem. With >, example 1 would remove 2 intervals instead of 1.

Starting lastEnd at 0

✗ int lastEnd = 0;

✓ int lastEnd = INT_MIN;

Starts can be negative (down to −5·10^4). With lastEnd = 0, an interval like [-5, -1] would wrongly look like it overlaps.

Counting overlapping pairs

The answer is not the number of pairs that overlap. One long interval can overlap 5 others; removing just that one fixes all 5 pairs. Count what you keep, then subtract from n.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture