Non-overlapping Intervals

Problem Description

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

Examples

Constraints

• 1 ≤ intervals.length ≤ 10⁵
• intervals[i].length == 2
• -5 * 10⁴ ≤ start < end ≤ 5 * 10⁴

Choosing to Keep the Interval with the Earliest End Time

This is a classic variation of the Interval Scheduling problem. Instead of choosing which intervals to remove, we can rephrase the problem: what is the maximum number of non-overlapping intervals we can keep? The minimum intervals to remove is then total_intervals - max_intervals_kept.

To maximize the intervals we keep, we must be greedy: we should always choose the interval that finishes as early as possible (the smallest end value). This leaves the maximum possible room for subsequent intervals to fit.

• Sort the intervals by their end coordinates in ascending order.
• Maintain a pointer end representing the finish time of the last kept interval.
• Iterate through the sorted list. If the current interval’s start value is greater than or equal to end, we can keep this interval and update end = current_end.
• If it starts before end, they overlap. We must discard this interval, incrementing our removal counter.

Solution 1: Greedy Interval Scheduling

Sort the intervals by their end coordinate. Track the last finish time to detect and count overlaps.

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // sort by end coordinate in ascending order
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

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

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                // no overlap: keep this interval and update finish time
                end = intervals[i][1];
            } else {
                // overlap: must discard the current interval
                removals++;
            }
        }

        return removals;
    }
}

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0

        # sort by end coordinate in ascending order
        intervals.sort(key=lambda x: x[1])

        end = intervals[0][1]
        removals = 0

        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                # no overlap: keep this interval and update finish time
                end = intervals[i][1]
            else:
                # overlap: must discard the current interval
                removals += 1

        return removals

#include <vector>
#include <algorithm>

class Solution {
public:
    int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        // sort by end coordinate in ascending order
        std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

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

        for (size_t i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= end) {
                // no overlap: keep this interval and update finish time
                end = intervals[i][1];
            } else {
                // overlap: must discard the current interval
                removals++;
            }
        }

        return removals;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n) where n is the number of intervals. Sorting dominates the execution time. The scan is a linear O(n) pass.
• Space Complexity: O(n) or O(log n) depending on the sorting implementation memory stack.

Where it breaks: Nothing breaks for standard ranges. If you sort by start coordinates instead of end coordinates, you must write complex logic to decide which overlapping interval to discard when an overlap is found (you always discard the one with the larger end coordinate). Sorting by end coordinates naturally resolves this.

Common Mistakes

• Sorting by start coordinates instead of end coordinates. Sorting by start coordinates is valid but requires more complex logic: when an overlap occurs, you must discard the interval that extends further right (larger end) to minimize future conflicts. Sorting by end coordinates handles this sorting constraint naturally.
• Counting boundaries touching as overlaps. The problem description states that intervals like [1, 2] and [2, 3] are non-overlapping. The inequality must check >= (intervals[i][0] >= end), not strictly >.
• Forgetting the empty or single-element edge cases. Ensure the base checks return 0 immediately to prevent crashes when accessing index 0.

Frequently Asked Questions

Can we solve this by sorting by start coordinates? Yes. If sorted by start coordinates, you check if current_start < last_end. If true, you have an overlap and must increment removals. You then update last_end = min(last_end, current_end) to keep the interval that finishes earlier. This is also O(n log n) and O(1) space.

What is the difference between this and Merge Intervals? Merge Intervals combines overlapping ranges to cover the same span. This problem deletes ranges to ensure no overlap exists.

What does this problem test in interviews? It tests your ability to apply greedy scheduling theorems (Interval Scheduling) and manage boundary overlaps.

← All Problems