Non-overlapping Intervals

How it works

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.

Steps

1. Sort all intervals by their end time.
2. Initialize:
   • prevEnd as the end of the first interval
   • res = 0 to count how many intervals we remove
3. Iterate through the intervals starting from the second one:
4. 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
5. After processing all intervals, return res

Complexity

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

Things to watch for

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.

from typing import List

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

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
            return a[1] < b[1];
        });
        int res = 0;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if (start < prevEnd) {
                res++;
            } else {
                prevEnd = end;
            }
        }
        return res;
    }
};