Skip to main content
CodePeetCodePeet
BLIND 75

Non-overlapping Intervals

MEDIUMProblemSolveExternal Links

Description

You are given an array of intervals where each interval is represented as a pair [start, end]. Your task is to determine the minimum number of intervals you need to remove so that the remaining intervals do not overlap with each other.

Two intervals are considered non-overlapping if they merely touch at a single point. For instance, [1, 2] and [2, 3] are non-overlapping because they only share the boundary point 2, but [1, 3] and [2, 4] overlap because they share the range from 2 to 3.

Examples

Example 1

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

Output: 1

Explanation: If we remove the interval [1,3], the remaining intervals [1,2], [2,3], and [3,4] do not overlap — each one ends exactly where the next begins. Removing just one interval is sufficient to eliminate all overlaps.

Example 2

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

Output: 2

Explanation: All three intervals are identical — they all cover the range [1,2]. We can keep only one of them. Removing two intervals leaves a single [1,2] with no overlaps.

Example 3

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

Output: 0

Explanation: The two intervals only touch at the point 2. Since touching at a single point does not count as overlapping, no removal is needed.

Constraints

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

Editorial

Brute Force

Intuition

The most direct way to think about this problem is: try every possible subset of intervals, check which subsets have no overlaps, and among those valid subsets, find the one with the most intervals. The answer is then the total number of intervals minus the size of the largest non-overlapping subset.

However, checking all subsets is extremely expensive (2^n subsets), so a more practical brute force uses sorting combined with a comparison of every pair.

A more reasonable brute force approach: sort the intervals by their start times, then for each interval decide whether to keep it or remove it. If we keep it, we check it against all subsequent intervals. If any subsequent interval overlaps with it, we compare the cost of removing the current interval versus removing the overlapping one.

The simplest implementable brute force: sort by start time, then use a nested loop to greedily resolve each overlap by removing the interval that extends further to the right (since that one is more likely to cause future overlaps). This is actually a greedy idea but implemented with a sort-by-start approach.

Step-by-Step Explanation

Let's trace through with intervals = [[1,2],[2,3],[3,4],[1,3]], using the brute force approach of sorting by start time and greedily resolving overlaps:

Step 1: Sort intervals by start time: [[1,2],[1,3],[2,3],[3,4]].

Step 2: Compare interval [1,2] with [1,3]. They overlap (both start at 1). The one ending later is [1,3] (end=3 > end=2). Keep [1,2], mark [1,3] for removal. removals=1.

Step 3: Compare interval [1,2] with [2,3]. Start of [2,3] is 2 which equals end of [1,2]. They only touch — no overlap. Move on.

Step 4: Compare interval [2,3] with [3,4]. Start of [3,4] is 3 which equals end of [2,3]. They only touch — no overlap.

Step 5: All overlaps resolved. Total removals = 1.

Result: 1

Brute Force — Sort by Start and Resolve Overlaps — Watch how we sort intervals by start time and resolve each overlap by removing the interval that ends later, since it's more likely to cause future conflicts.

Algorithm

  1. Sort intervals by start time
  2. Initialize prev_end to the end of the first interval, removals = 0
  3. For each subsequent interval [start, end]:
    • If start < prev_end (overlap detected):
      • Increment removals
      • Keep the interval that ends earlier: prev_end = min(prev_end, end)
    • Else (no overlap):
      • Update prev_end = end
  4. Return removals

Code

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 < intervals.size(); i++) {
            if (intervals[i][0] < prevEnd) {
                removals++;
                prevEnd = min(prevEnd, intervals[i][1]);
            } else {
                prevEnd = intervals[i][1];
            }
        }
        
        return removals;
    }
};
class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort()
        
        removals = 0
        prev_end = intervals[0][1]
        
        for start, end in intervals[1:]:
            if start < prev_end:
                removals += 1
                prev_end = min(prev_end, end)
            else:
                prev_end = end
        
        return removals
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(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;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the intervals takes O(n log n). The subsequent single pass through the sorted intervals takes O(n). The dominant term is O(n log n).

Space Complexity: O(log n)

The sorting algorithm uses O(log n) stack space. Beyond that, we only use a constant number of extra variables.

Why This Approach Is Not Efficient

The sort-by-start approach actually achieves the same time complexity O(n log n) as the optimal approach and produces correct results when we always keep the interval that ends earlier during an overlap. However, the reasoning is less clean and can lead to subtle bugs.

The core issue with sorting by start time: when two intervals have the same start time, the order can affect which one we examine first. We need the extra min(prevEnd, end) logic to handle overlaps correctly — essentially choosing to keep the shorter interval. This works, but the logic is harder to reason about.

The key insight for a cleaner solution: if we sort by end time instead, the greedy choice becomes simpler and more elegant. By processing intervals in order of when they finish, we always keep the interval that ends earliest. This leaves the maximum possible room for subsequent intervals and eliminates the need for the min comparison during overlap resolution. The greedy structure becomes: if no overlap, keep it; if overlap, automatically skip it (the current interval ends later than the one we already kept).

Optimal Approach - Greedy with Sort by End Time

Intuition

Think of this problem like scheduling meetings in a single conference room. You have a list of requested meetings, each with a start and end time. Some meetings conflict with each other — they overlap in time. You want to accept as many meetings as possible (equivalently, cancel as few as possible).

Which meeting should you prefer when there's a conflict? The one that finishes earliest! If a meeting ends at 2pm instead of 5pm, it frees up the room much sooner, allowing more subsequent meetings to fit in.

This is the classic Activity Selection greedy strategy:

  1. Sort all intervals by their end time (ascending)
  2. Keep the first interval (it ends earliest among all)
  3. For each subsequent interval, if it starts at or after the end of the last kept interval, keep it. Otherwise, skip it (it overlaps with one we already kept that ends earlier).

The brilliance of sorting by end time is that the greedy choice becomes trivial: if an interval doesn't overlap, keep it. If it overlaps, skip it — because the interval we already kept ends earlier, and we sorted by end time, so the kept interval is always the better choice.

The answer is total intervals - intervals kept, which equals the number of removals.

Step-by-Step Explanation

Let's trace through with intervals = [[1,2],[2,3],[3,4],[1,3]]:

Step 1: Sort by end time: [[1,2],[2,3],[1,3],[3,4]].

  • [1,2] ends at 2
  • [2,3] ends at 3
  • [1,3] ends at 3
  • [3,4] ends at 4

Step 2: Initialize: prev_end = -∞, removals_count = 4 (assume all need removal), we'll subtract for each one we keep.

Step 3: Process [1,2]: start=1 ≥ prev_end=-∞? Yes. Keep it. removals_count = 4-1 = 3. Update prev_end = 2.

Step 4: Process [2,3]: start=2 ≥ prev_end=2? Yes (touching is not overlapping). Keep it. removals_count = 3-1 = 2. Update prev_end = 3.

Step 5: Process [1,3]: start=1 ≥ prev_end=3? No (1 < 3). This interval overlaps with one we already kept. Skip it (remove it). removals_count stays 2.

Step 6: Process [3,4]: start=3 ≥ prev_end=3? Yes. Keep it. removals_count = 2-1 = 1. Update prev_end = 4.

Step 7: All intervals processed. removals_count = 1. We kept [1,2], [2,3], [3,4] and removed [1,3].

Result: 1

Greedy — Sort by End Time and Select Non-Overlapping Intervals — Watch how sorting by end time lets us greedily keep the earliest-finishing intervals, automatically skipping any that overlap with our selections.

Algorithm

  1. Sort intervals by their end time in ascending order
  2. Initialize prev_end = -∞ (negative infinity) and removals = len(intervals)
  3. For each interval [start, end] in the sorted list:
    • If start ≥ prev_end (no overlap, touching is fine):
      • Keep this interval: decrement removals
      • Update prev_end = end
    • Else: skip this interval (it's removed)
  4. Return removals

Code

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 removals = intervals.size();
        int prevEnd = INT_MIN;
        
        for (auto& interval : intervals) {
            if (interval[0] >= prevEnd) {
                removals--;
                prevEnd = interval[1];
            }
        }
        
        return removals;
    }
};
class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        
        removals = len(intervals)
        prev_end = float('-inf')
        
        for start, end in intervals:
            if start >= prev_end:
                removals -= 1
                prev_end = end
        
        return removals
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        int removals = intervals.length;
        int prevEnd = Integer.MIN_VALUE;
        
        for (int[] interval : intervals) {
            if (interval[0] >= prevEnd) {
                removals--;
                prevEnd = interval[1];
            }
        }
        
        return removals;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the intervals by end time takes O(n log n). The subsequent single pass through the sorted list takes O(n) — each interval is examined exactly once with an O(1) comparison. The overall time is dominated by the sort: O(n log n).

Space Complexity: O(log n)

The sorting algorithm uses O(log n) auxiliary space for its internal recursion stack. We only use two extra variables (prev_end and removals), which is O(1). The total auxiliary space is O(log n).