Non-overlapping Intervals

medium
IntervalsArrayIntervalGreedySorting

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 considered non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Examples

Example 1

  • Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
  • Output: 1
  • Explanation: Removing [1,3] makes the rest of the intervals non-overlapping.

Example 2

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

Example 3

  • Input: intervals = [[1,2],[2,3]]
  • Output: 0
  • Explanation: The intervals are already non-overlapping.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Greedy (Sort by End Time)

Intuition

This is the classic interval scheduling problem. The greedy strategy is to always keep the interval that ends earliest, because it leaves the most room for future intervals. We sort all intervals by their end time, then greedily select non-overlapping intervals. For each interval, if its start is greater than or equal to the end of the last selected interval, we keep it. Otherwise, we must remove it. The answer is the total number of intervals minus the count of intervals we kept.

Algorithm

  1. Sort the intervals by their end time in ascending order.
  2. Initialize a counter `kept` to 1 (we always keep the first interval) and set `prevEnd` to the end of the first interval.
  3. For each subsequent interval, check if its start is >= `prevEnd`.
  4. If yes, it does not overlap. Increment `kept` and update `prevEnd` to this interval's end.
  5. If no, it overlaps with the previously kept interval. Skip it (it will be removed).
  6. Return `intervals.length - kept`.
TimeO(n log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        int kept = 1;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < (int)intervals.size(); i++) {
            if (intervals[i][0] >= prevEnd) {
                kept++;
                prevEnd = intervals[i][1];
            }
        }

        return intervals.size() - kept;
    }
};
Java 21
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int kept = 1;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= prevEnd) {
                kept++;
                prevEnd = intervals[i][1];
            }
        }

        return intervals.length - kept;
    }
}
Python 3.12
def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1])

    kept = 1
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] >= prev_end:
            kept += 1
            prev_end = intervals[i][1]

    return len(intervals) - kept
Go 1.26
import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    kept := 1
    prevEnd := intervals[0][1]

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= prevEnd {
            kept++
            prevEnd = intervals[i][1]
        }
    }

    return len(intervals) - kept
}
Approach 2

Greedy (Sort by Start Time)

Intuition

An alternative greedy approach sorts by start time. When two intervals overlap, we always remove the one with the larger end time, because it is more likely to cause future conflicts. We scan through the sorted intervals, and whenever an overlap occurs (current start < previous end), we increment the removal count and keep the interval that ends earlier. This achieves the same result as sorting by end time but uses a different mental model that some find more intuitive.

Algorithm

  1. Sort the intervals by their start time. Break ties by end time.
  2. Initialize `removals` to 0 and `prevEnd` to the end of the first interval.
  3. For each subsequent interval:
  4. Return `removals`.
TimeO(n log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        int removals = 0;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < (int)intervals.size(); i++) {
            if (intervals[i][0] < prevEnd) {
                removals++;
                prevEnd = min(prevEnd, intervals[i][1]);
            } else {
                prevEnd = intervals[i][1];
            }
        }

        return removals;
    }
};
Java 21
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int removals = 0;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prevEnd) {
                removals++;
                prevEnd = Math.min(prevEnd, intervals[i][1]);
            } else {
                prevEnd = intervals[i][1];
            }
        }

        return removals;
    }
}
Python 3.12
def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    intervals.sort()

    removals = 0
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:
            removals += 1
            prev_end = min(prev_end, intervals[i][1])
        else:
            prev_end = intervals[i][1]

    return removals
Go 1.26
import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    removals := 0
    prevEnd := intervals[0][1]

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < prevEnd {
            removals++
            if intervals[i][1] < prevEnd {
                prevEnd = intervals[i][1]
            }
        } else {
            prevEnd = intervals[i][1]
        }
    }

    return removals
}

Frequently asked questions

What is the optimal time complexity of Non-overlapping Intervals?

The most efficient approach in this guide ("Greedy (Sort by Start Time)") runs in O(n log n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Non-overlapping Intervals use?

Non-overlapping Intervals is a medium-level Intervals problem involving Array, Interval, Greedy. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Non-overlapping Intervals be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
intervals=
[[1,2],[2,3],[3,4],[1,3]]
Expected Output
1