Non-overlapping Intervals — Minimum Removals

Key Insight

This is the flip side of Activity Selection. Max non-overlapping = N, so removals = N - maxKept. Sort by end time, greedily keep intervals that don't overlap, count the rest as removals.

The Algorithm

sort by end time
kept = 1, lastEnd = intervals[0].end
for each remaining interval:
if start >= lastEnd: keep it
else: remove it (overlap)
return N - kept

Interactive Visualization

Considering

Kept

Removed

Step 0 of 0

Kept

Removed

Last End

—

Total

Ready. Press Play or Next to start.

✓ Done

Speed

C++ — Non-overlapping Intervals

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b){ return a[1] < b[1]; });

    int kept = 1, lastEnd = intervals[0][1];

    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] >= lastEnd) {
            kept++;
            lastEnd = intervals[i][1];
        }
    }
    return intervals.size() - kept;
}

Complexity

Time

O(N log N)

Sorting + single pass.

Space

O(1)

In-place after sorting.

📝 Notes

▼