435. Non-overlapping Intervals

← All Problems
medium Intervals
Given an array of 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. Intervals that only touch at a point are considered non-overlapping — for example, [1,2] and [2,3] do not overlap.

Example

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

Output: 1

Removing just [1,3] is enough to make the remaining intervals [1,2], [2,3], and [3,4] non-overlapping. The interval [1,3] overlaps with both [1,2] and [2,3], so removing it solves all conflicts at once.

Sort intervals by end time. Greedily keep the interval that ends earliest — this leaves the most room for future intervals and maximizes the number you can keep. Whenever the next interval's start is before the current end, it overlaps and must be removed. Count those removals.

Why this works

Sorting by end time is the key insight. By always keeping the interval that ends earliest, you leave the maximum room for future intervals. Any interval that overlaps with a kept interval must be removed – and since we chose the earliest-ending one, we are guaranteed to minimize total removals. This is a classic greedy activity selection approach.

Step by step

  1. Sort by end time — this lets the greedy strategy work: always prefer the interval that finishes earliest.
  2. Track the end of the last kept interval — start with negative infinity so the first interval is always kept.
  3. For each interval — if it starts at or after the previous end, keep it (update prev_end). Otherwise, it overlaps, so count a removal.
  4. Return the removal count — this is the minimum number of intervals to remove for zero overlap.
Time: O(n·log n) Space: O(1) 
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // sort by end time for greedy
        int removals = 0;
        int prevEnd = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] >= prevEnd) { // no overlap — keep this interval
                prevEnd = interval[1];
            } else {
                removals++; // overlap — remove this one (it ends later)
            }
        }
        return removals;
    }
}

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]; // sort by end time for greedy
        });
        int removals = 0;
        int prevEnd = INT_MIN;
        for (auto& interval : intervals) {
            if (interval[0] >= prevEnd) { // no overlap — keep this interval
                prevEnd = interval[1];
            } else {
                removals++; // overlap — remove this one (it ends later)
            }
        }
        return removals;
    }
};

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # sort by end time to apply greedy strategy
    removals = 0
    prev_end = float('-inf')
    for start, end in intervals:
        if start >= prev_end:  # no overlap — keep this interval
            prev_end = end
        else:
            removals += 1  # overlap — remove this one (it ends later)
    return removals