84. Non-overlapping Intervals

MediumGreedy & IntervalsAlso on LeetCode ↗

Return the minimum number of intervals to remove so the rest do not overlap. Intervals that only touch (like [1,2] and [2,3]) do not overlap.

Example 1

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

Output: 1

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]

Output: 2

Hint 1

Keeping the interval that ends earliest leaves the most room for the rest.

Hint 2

This is the classic activity-selection greedy.

GreedyIntervalsSorting

Reference solution for Greedy by end time (time O(n log n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])     # earliest end first
        removed, end = 0, float('-inf')
        for s, e in intervals:
            if s >= end:
                end = e                        # keep it
            else:
                removed += 1                   # overlaps the last kept interval
        return removed

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));   // earliest end first
        int removed = 0;
        long end = Long.MIN_VALUE;
        for (int[] iv : intervals) {
            if (iv[0] >= end) end = iv[1]; else removed++;
        }
        return removed;
    }
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
        int removed = 0;
        long long end = LLONG_MIN;
        for (auto& iv : intervals) {
            if (iv[0] >= end) end = iv[1]; else removed++;
        }
        return removed;
    }
};

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]); // earliest end first
  let removed = 0, end = -Infinity;
  for (const [s, e] of intervals) {
    if (s >= end) end = e; else removed++;
  }
  return removed;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

84. Non-overlapping Intervals

Example 1

Example 2

Approach 1: Greedy by end time ✅