Non-overlapping Intervals

LeetCode 435: Non-overlapping Intervals Solution & Explanation

Problem Overview

TL;DR: Sort intervals by increasing end time, greedily keep every interval that starts at or after the end of the last kept interval, and return the number of intervals not kept.

In LeetCode 435: Non-overlapping Intervals, the goal is to remove the minimum number of intervals so that every remaining pair is non-overlapping. Two intervals may touch at an endpoint, so an interval starting exactly at the previous end is valid.

For example, [1,3] and [3,6] do not overlap because 3 is a shared endpoint rather than an interior overlap. This popular interview question is an interval scheduling problem, and the optimal solution for interviews uses a greedy choice based on the earliest finishing interval.

Brute Force Approach for Non-overlapping Intervals

A naive approach considers every possible subset of intervals:

1. Choose a subset of the input intervals to keep.
2. Check whether the selected intervals are pairwise non-overlapping.
3. Track the largest valid subset.
4. Return:

total intervals - largest valid subset size

A recursive version can either keep or remove each interval.

Naive Pseudocode

function search(index, selectedIntervals):
    if index == number of intervals:
        if selectedIntervals is non-overlapping:
            update largestValidCount
        return

    search(index + 1, selectedIntervals)          // Remove current interval

    add intervals[index] to selectedIntervals
    search(index + 1, selectedIntervals)          // Keep current interval
    remove intervals[index] from selectedIntervals

The recursion explores 2^n subsets. If each completed subset is checked by comparing its intervals, the total complexity is at least exponential and can approach:

O(2^n * n^2)

depending on how the overlap check is implemented.

With n as large as 10^5, this approach cannot finish. It will exceed time limits long before reaching the required input size. The main issue is that it repeatedly evaluates many combinations even though the interval structure allows a local greedy decision.

Algorithm Strategy: Greedy Patterns

1. Sort the intervals by their end coordinate in ascending order.
2. Set the end boundary of the last accepted interval.
3. Scan the sorted intervals from left to right.
4. If the current interval starts before the tracked boundary, it overlaps an accepted interval, so remove it.
5. Otherwise, accept it and update the boundary to the current interval's end.
6. Return the number of removed intervals.

The sorted order ensures that when an overlap occurs, the already accepted interval has the earliest possible end among the intervals being considered. This preserves the most room for future intervals.

Execution Flow

1. Sort intervals using their end values.
   • For example, intervals ending at 3, 4, and 7 are processed in that order.
2. Initialize the last accepted end boundary.
3. Read the next interval:
   • If start < lastEnd, the interval overlaps the current schedule.
   • Increment the removal count.
   • Do not update lastEnd.
4. If start >= lastEnd:
   • Keep the interval.
   • Set lastEnd = end.
5. Continue until every interval has been processed.
6. Return the removal count.

For example, with:

[[1,4], [2,3], [5,7], [6,8]]

After sorting by end:

[[2,3], [1,4], [5,7], [6,8]]

The execution is:

• Keep [2,3]; lastEnd = 3.
• [1,4] starts before 3; remove it.
• Keep [5,7]; lastEnd = 7.
• [6,8] starts before 7; remove it.
• Total removed: 2.

Proof of Correctness

We prove that the greedy algorithm removes the minimum number of intervals.

Claim 1: The selected intervals are always non-overlapping

An interval is selected only when:

start >= lastEnd

Therefore, its start is at or after the end of the previously selected interval. Since intervals are processed in end-sorted order, every newly selected interval is compatible with the current selection. Thus, the selected set is non-overlapping.

Claim 2: Choosing the earliest ending compatible interval is safe

Consider any point during the scan where multiple intervals could be selected next. Let the greedy algorithm choose interval G, whose end is the smallest among the available choices.

For any other possible next interval X:

G.end <= X.end

Every interval that can be scheduled after X must start at or after X.end. Because G.end is no larger, every interval compatible with X is also compatible with G. Therefore, replacing X with G cannot reduce the number of intervals that can be selected later.

Claim 3: The greedy algorithm keeps the maximum possible number of intervals

By repeatedly selecting the earliest finishing compatible interval, the algorithm makes a safe choice at every step. Claim 2 shows that each choice preserves an optimal continuation. Therefore, the final selected set has maximum possible size.

If the input contains n intervals and the algorithm keeps k of them, then the minimum number that must be removed is:

n - k

Thus, the algorithm returns the minimum removal count.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 2406: Divide Intervals Into Minimum Number of Groups
• LeetCode 57: Insert Interval
• LeetCode 56: Merge Intervals

These problems all organize interval boundaries and maintain scheduling or merging constraints while scanning ordered data. LeetCode 2406 tracks simultaneous active intervals, while LeetCode 57 and LeetCode 56 process intervals in boundary order to preserve or combine compatible ranges. LeetCode 435 uses the same interval-processing foundation but applies the earliest-finish greedy rule to maximize the number of retained intervals.

Reference Implementation

C++ Solution for LeetCode 435

1class Solution {
2public:
3    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
4        if (intervals.empty()) {
5            return 0;
6        }
7
8        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
9            return a[1] < b[1];
10        });
11
12        int removed = 0;
13        int lastEnd = intervals[0][1];
14
15        for (int i = 1; i < static_cast<int>(intervals.size()); ++i) {
16            if (intervals[i][0] < lastEnd) {
17                ++removed;
18            } else {
19                lastEnd = intervals[i][1];
20            }
21        }
22
23        return removed;
24    }
25};

This implementation sorts by end time, initializes the boundary with the first interval's end, and counts every later interval whose start is strictly less than that boundary.

Java Solution for LeetCode 435

1class Solution {
2    public int eraseOverlapIntervals(int[][] intervals) {
3        java.util.Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
4
5        int kept = 0;
6        int lastEnd = 0;
7        boolean hasLastEnd = false;
8
9        for (int[] interval : intervals) {
10            int start = interval[0];
11            int end = interval[1];
12
13            if (!hasLastEnd || start >= lastEnd) {
14                kept++;
15                lastEnd = end;
16                hasLastEnd = true;
17            }
18        }
19
20        return intervals.length - kept;
21    }
22}

This version counts the number of intervals kept instead of directly counting removals. The final result is:

total intervals - kept intervals

The hasLastEnd flag handles initialization without relying on an artificial boundary value.

Python Solution for LeetCode 435

1from typing import List, Optional
2
3
4class Solution:
5    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
6        intervals.sort(key=lambda interval: interval[1])
7
8        kept = 0
9        last_end = None
10
11        for start, end in intervals:
12            if last_end is None or start >= last_end:
13                kept += 1
14                last_end = end
15
16        return len(intervals) - kept

This implementation follows the same earliest-finish greedy strategy. It uses None to represent that no interval has been accepted yet, then updates last_end only when an interval is kept.