435. Non Overlapping Intervals - Explanation

Description

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: Intervals are non-overlapping even if they have a common point. For example, [1, 3] and [2, 4] are overlapping, but [1, 2] and [2, 3] are non-overlapping.

Example 1:

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

Output: 1

Explanation: After [1,4] is removed, the rest of the intervals are non-overlapping.

Example 2:

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

Output: 0

Constraints:

1 <= intervals.length <= 1000
intervals[i].length == 2
-50000 <= starti < endi <= 50000

Recommended Time & Space Complexity

You should aim for a solution with O(nlogn) time and O(n) space, where n is the size of the input array.

Hint 1

If two intervals are sorted in ascending order by their start values, they overlap if the start value of the second interval is less than the end value of the first interval. And these are called overlapping intervals.

Hint 2

A brute force approach would be to sort the given intervals in ascending order based on their start values and recursively explore all possibilities. This would be an exponential approach. Can you think of a better way? Maybe a greedy approach works here.

Hint 3

We first sort the given intervals based on their start values to efficiently check for overlaps by comparing adjacent intervals. We then iterate through the sorted intervals from left to right, keeping track of the previous interval’s end value as prevEnd, initially set to the end value of the first interval.

Hint 4

We then iterate from the second interval. If the current interval doesn't overlap, we update prevEnd to the current interval's end and continue. Otherwise, we set prevEnd to the minimum of prevEnd and the current interval’s end, greedily removing the interval that ends last to retain as many intervals as possible.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

We want to remove the minimum number of intervals so that the remaining intervals do not overlap.

A helpful way to think about this is:

instead of directly counting removals, we can try to keep as many non-overlapping intervals as possible
if we know the maximum number of intervals we can keep without overlap, then:
- minimum removals = total intervals - maximum kept

To make decisions, we sort the intervals by start time and use recursion to explore two choices at each interval:

Skip the current interval
Take the current interval (only if it does not overlap with the previously taken interval)

The recursive function represents:
"What is the maximum number of non-overlapping intervals we can keep starting from index i, given that the last chosen interval is prev?"

Algorithm

Sort the intervals by their start time.
Define a recursive function dfs(i, prev):
- i is the current interval index
- prev is the index of the last chosen interval (-1 if none chosen yet)
Base case:
- If i reaches the end of the list, return 0 (no more intervals to take)
Option 1: Skip the current interval:
- res = dfs(i + 1, prev)
Option 2: Take the current interval (only if it doesn't overlap):
- If prev == -1 or intervals[prev][1] <= intervals[i][0]:
  - res = max(res, 1 + dfs(i + 1, i))
Return res, the maximum number of intervals we can keep from this state.
Compute kept = dfs(0, -1)
Return len(intervals) - kept as the minimum number of intervals to remove.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        def dfs(i, prev):
            if i == len(intervals):
                return 0
            res = dfs(i + 1, prev)
            if prev == -1 or intervals[prev][1] <= intervals[i][0]:
                res = max(res, 1 + dfs(i + 1, i))
            return res

        return len(intervals) - dfs(0, -1)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

We want to remove the minimum number of intervals so that the remaining intervals do not overlap.

A common trick is to flip the problem:

instead of counting removals directly, find the maximum number of non-overlapping intervals we can keep
then:
- minimum removals = total intervals - maximum kept

This solution sorts intervals by end time. After that, for any interval i, the next interval we choose must start at or after intervals[i][1].

We define a DP state that answers:
"If we choose interval i as part of our set, what is the maximum number of non-overlapping intervals we can take starting from i?"

The result for an index depends on future indices, and many states repeat, so we use memoization.

Algorithm

Sort the intervals by their end time.
Let n be the number of intervals.
Use a memo map memo to store results for each index i.
Define a recursive function dfs(i):
- returns the maximum number of non-overlapping intervals we can take
  starting with interval i included
If i is already in memo, return the stored value.
Initialize res = 1 because we are taking interval i.
Try to extend the chain by choosing a next interval j where j > i:
- only valid if intervals[i][1] <= intervals[j][0]
- if valid, update:
  - res = max(res, 1 + dfs(j))
Store res in memo[i] and return it.
The maximum kept intervals is computed as dfs(0).
Return n - dfs(0) as the minimum number of intervals to remove.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: x[1])
        n = len(intervals)
        memo = {}

        def dfs(i):
            if i in memo:
                return memo[i]

            res = 1
            for j in range(i + 1, n):
                if intervals[i][1] <= intervals[j][0]:
                    res = max(res, 1 + dfs(j))
            memo[i] = res
            return res

        return n - dfs(0)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

We want to remove the minimum number of intervals so that the remaining intervals do not overlap.

A useful trick is to instead find the maximum number of non-overlapping intervals we can keep.
Once we know that:

minimum removals = total intervals - maximum kept

After sorting intervals by end time, we can build a DP array where:

dp[i] = the maximum number of non-overlapping intervals we can keep ending at interval i (meaning interval i is included)

To compute dp[i], we look at all earlier intervals j < i:

if interval j ends before interval i starts, they can both be kept
so we can extend the chain: 1 + dp[j]

Algorithm

Sort the intervals by their end time.
Let n be the number of intervals.
Create an array dp of size n.
For each interval index i from 0 to n - 1:
- Start with dp[i] = 1 (we can always keep interval i alone)
- For every earlier interval j from 0 to i - 1:
  - If intervals[j][1] <= intervals[i][0]:
    - update dp[i] = max(dp[i], 1 + dp[j])
After filling dp, the maximum number of non-overlapping intervals we can keep is:
- max_non_overlapping = max(dp)
Return the minimum removals:
- n - max_non_overlapping

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        dp = [0] * n

        for i in range(n):
            dp[i] = 1
            for j in range(i):
                if intervals[j][1] <= intervals[i][0]:
                    dp[i] = max(dp[i], 1 + dp[j])

        max_non_overlapping = max(dp)
        return n - max_non_overlapping

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Dynamic Programming (Binary Search)

Intuition

We want to remove the minimum number of intervals so that the remaining intervals do not overlap.

A common trick is to flip the goal:

instead of counting removals directly, find the maximum number of non-overlapping intervals we can keep
then:
- minimum removals = total intervals - maximum kept

After sorting intervals by end time, consider interval i:

we have two choices:
1. skip interval i → keep the best answer up to i - 1
2. take interval i → then we must take it after the last interval that ends
  before intervals[i][0]

The slow part is finding that "previous compatible interval".
Because the intervals are sorted by end time, we can find it using binary search.

We maintain:

dp[i] = maximum number of non-overlapping intervals we can keep using intervals 0..i

Algorithm

Sort the intervals by their end time.
Create a DP array dp of size n:
- dp[i] stores the maximum number of non-overlapping intervals we can keep
  among the first i + 1 intervals
Set dp[0] = 1 since we can always keep the first interval.
For each interval i from 1 to n - 1:
Use binary search to find idx:
- the first position in [0, i) where intervals[pos][1] > intervals[i][0]
- so idx - 1 is the last interval that does not overlap with interval i
Update dp[i]:
- If no compatible interval exists (idx == 0):
  - we can only take interval i alone, so compare with skipping:
    - dp[i] = dp[i - 1]
- Otherwise:
  - Option 1: skip interval i → dp[i - 1]
  - Option 2: take interval i → 1 + dp[idx - 1]
  - dp[i] = max(dp[i - 1], 1 + dp[idx - 1])
After filling DP, the maximum kept is dp[n - 1].
Return n - dp[n - 1] as the minimum number of intervals to remove.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        dp = [0] * n
        dp[0] = 1

        def bs(r, target):
            l = 0
            while l < r:
                m = (l + r) >> 1
                if intervals[m][1] <= target:
                    l = m + 1
                else:
                    r = m
            return l

        for i in range(1, n):
            idx = bs(i, intervals[i][0])
            if idx == 0:
                dp[i] = dp[i - 1]
            else:
                dp[i] = max(dp[i - 1], 1 + dp[idx - 1])
        return n - dp[n - 1]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

5. Greedy (Sort By Start)

Intuition

We want to remove the minimum number of intervals so that the remaining intervals do not overlap.

A greedy strategy works well here. After sorting intervals by their start time, we process them from left to right and always keep the interval that ends earlier when an overlap occurs.

Why this works:

When two intervals overlap, keeping the one with the smaller end time leaves more room for future intervals
Removing the interval with the larger end is always a worse choice, because it blocks more upcoming intervals

So instead of choosing which interval to keep globally, we make a local greedy decision whenever an overlap happens.

Algorithm

Sort the intervals by their start time.
Initialize:
- prevEnd as the end of the first interval
- res = 0 to count how many intervals we remove
Iterate through the remaining intervals one by one:
For each interval (start, end):
- If start >= prevEnd:
  - There is no overlap
  - Update prevEnd = end
- Else (overlap exists):
  - We must remove one interval
  - Increment res
  - Keep the interval with the smaller end:
    - prevEnd = min(end, prevEnd)
After processing all intervals, return res

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res = 0
        prevEnd = intervals[0][1]

        for start, end in intervals[1:]:
            if start >= prevEnd:
                prevEnd = end
            else:
                res += 1
                prevEnd = min(end, prevEnd)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

6. Greedy (Sort By End)

Intuition

We want to remove the minimum number of intervals so that the remaining intervals do not overlap.

A very clean greedy idea is to always keep the interval that ends earliest.
Why? Because an interval that ends earlier leaves more room for future intervals, reducing the chance of overlap later.

So instead of deciding which intervals to remove directly, we:

sort all intervals by their end time
walk through them from left to right
keep track of the end of the last interval we decided to keep

Whenever we see an overlap:

we remove the current interval
because it ends later than the one we already kept (due to sorting)

This greedy choice is optimal and ensures the maximum number of intervals are kept.

Algorithm

Sort all intervals by their end time.
Initialize:
- prevEnd as the end of the first interval
- res = 0 to count how many intervals we remove
Iterate through the intervals starting from the second one:
For each interval (start, end):
- If start < prevEnd:
  - The interval overlaps with the previous one
  - Remove this interval → increment res
- Else:
  - No overlap
  - Update prevEnd = end
After processing all intervals, return res

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda pair: pair[1])
        prevEnd = intervals[0][1]
        res = 0

        for i in range(1, len(intervals)):
            if prevEnd > intervals[i][0]:
                res += 1
            else:
                prevEnd = intervals[i][1]


        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Common Pitfalls

Sorting by the Wrong Criterion

Sorting by start time instead of end time (or vice versa without proper handling) leads to suboptimal solutions. While both can work, sorting by end time gives a cleaner greedy solution because the interval that ends earliest always leaves the most room for future intervals. Sorting by start time requires additional logic to handle overlaps correctly.

Incorrect Overlap Detection

Using < instead of <= (or vice versa) when checking for overlaps causes off-by-one errors. Intervals [1, 2] and [2, 3] do NOT overlap because one ends exactly where the other begins. The condition should be intervals[i][0] >= prevEnd for non-overlapping, not intervals[i][0] > prevEnd.

Counting Kept Intervals Instead of Removed

Confusing what to count leads to returning the wrong answer. The problem asks for the minimum number of intervals to REMOVE, not the maximum to keep. If you count intervals kept, remember to return n - kept as the final answer. This subtle difference causes many incorrect submissions.