DSAPrep
MediumIntervals

Non Overlapping Intervals

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 that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You do not need to remove any of the intervals since they are already non-overlapping.

Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start_i < end_i <= 5 * 10^4
View original on LeetCode ↗

Brute Force (Longest Non-Overlapping Chain via DP)

Time O(n²)Space O(n)

Removing the fewest intervals to leave a non-overlapping set is the same as keeping the largest possible non-overlapping subset. Sort by start, then for every interval compute the longest chain of non-overlapping intervals that can follow it (classic “longest increasing subsequence”-style DP): dp[i] = 1 + max(dp[j]) over every j that starts at or after intervals[i] ends. The answer is n minus the best chain length.

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda iv: iv[0])
        n = len(intervals)
        dp = [1] * n
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if intervals[j][0] >= intervals[i][1]:
                    dp[i] = max(dp[i], 1 + dp[j])
        return n - max(dp)

The nested loop compares every pair of intervals — O(n²) time, O(n) space for the dp array. Correct, but it recomputes overlap relationships that a single greedy pass can settle in one look-ahead.

Greedy: Sort by End, Keep Earliest Finisher

OptimalTime O(n log n)Space O(1)

Sort intervals by their end time. Greedily keep an interval whenever it starts at or after the end of the last interval kept — keeping the interval that finishes earliest always leaves the most room for future intervals, so this greedy choice never costs an optimal solution. Every interval that cannot be kept must be removed.

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda iv: iv[1])
        removals = 0
        prev_end = float('-inf')
        for start, end in intervals:
            if start >= prev_end:
                prev_end = end
            else:
                removals += 1
        return removals

Tracing intervals = [[1,2],[2,3],[3,4],[1,3]] sorted by end → [[1,2],[2,3],[1,3],[3,4]]:

Sorted intervals

[1, 2]
[2, 3]
[1, 3]
[3, 4]

Merged result

[1, 2]
1 / 4
mergingmerged

Sorted by end time. Keep [1,2] as the first non-overlapping interval. prev_end = 2.

Why sorting by end (not start) matters: the interval that ends earliest always leaves the most room for everything after it, so it is always safe to keep. Complexity: dominated by the sort → O(n log n) time; only a running counter and prev_end are tracked → O(1) extra space.