Non-overlapping Intervals

Non-overlapping Intervals flips the interval pattern around. Instead of joining overlaps, you delete some blocks so that none of them clash. The catch is you must delete as few as possible. This is a famous greedy question. Once you spot the trick, the code is tiny.

🎯 The Problem

You get a list of intervals and delete as few as possible so none clash.

• An interval is a pair: a start and an end. Some of them overlap.
• Remove the smallest number of intervals so the ones left never overlap.
• Return that count of removals.
• Two blocks overlap when one starts before the other ends.
• Touching at a point does not count. One ending at 2 and the next starting at 2 can both stay.

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

Explanation: Remove [1, 3] and the rest [[1, 2], [2, 3], [3, 4]] never overlap.
So only one removal is needed.

Here is the input drawn on a number line. The block [1, 3] cuts across both [1, 2] and [2, 3], so it is the troublemaker to drop.

You want to keep the most blocks you can, which is the same as removing the fewest.

🐢 Approach 1: Try Every Subset (Brute Force)

Test every possible clash-free group and keep the biggest.

The idea:

• Look at every subset of blocks.
• Keep only the subsets where no two blocks overlap.
• Find the biggest clash-free group. Removals are total minus that group size.

Why it is weak:

• With n blocks there are 2 to the power n subsets.
• That is exponential time.
• It becomes useless past a handful of blocks.

Here is the try-every-subset code:

def erase_overlap_intervals(intervals):
    n = len(intervals)
    best_keep = 0

    for mask in range(1 << n):
        chosen = [intervals[i] for i in range(n) if mask & (1 << i)]
        chosen.sort()
        if all(chosen[i][0] >= chosen[i - 1][1] for i in range(1, len(chosen))):
            best_keep = max(best_keep, len(chosen))

    return n - best_keep

⚡ Approach 2: Greedy, Sort By End (Best)

The idea in one line: always keep the block that ends soonest, because it leaves the most room for the rest.

The idea:

• Sort by end, not by start.
• A block that ends early frees the timeline early.
• This is a greedy choice: best local pick at each step. It is the classic activity selection idea.

How it works:

• Remember the end of the last block you kept.
• For each next block, ask: does it start before that kept end?
• If yes, it overlaps, so remove it and add one to the count. Leave the kept end alone.
• If no, it fits, so keep it and move the kept end to this block’s end.

Why it is fast:

• Sorting by end costs O(n log n). The sweep is O(n).
• The total is O(n log n), a huge jump from exponential.

Here is the greedy decision for each block after sorting by end.

Steps to Solve

1. Sort the intervals by their end value.
2. Set the kept end to the end of the first interval. Start the removal count at zero.
3. Walk through the rest. For each block, compare its start with the kept end.
4. If the start is less than the kept end, they overlap, so remove this block and add one to the count.
5. If the start is not less than the kept end, keep it and set the kept end to this block’s end.
6. Return the removal count.

#include <stdio.h>
#include <stdlib.h>

// compare by end for qsort
int cmp(const void *a, const void *b) {
    int *x = *(int **)a;
    int *y = *(int **)b;
    return x[1] - y[1];
}

int main(void) {
    int raw[][2] = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    int n = 4;

    int *arr[4];
    for (int i = 0; i < n; i++) arr[i] = raw[i];

    qsort(arr, n, sizeof(int *), cmp);  // sort by end

    int keptEnd = arr[0][1];
    int removals = 0;

    for (int i = 1; i < n; i++) {
        if (arr[i][0] < keptEnd) {   // overlap, must remove
            removals++;
        } else {                     // fits, keep it
            keptEnd = arr[i][1];
        }
    }

    printf("%d\n", removals);
    return 0;
}

1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int keptEnd = intervals[0][1];
    int removals = 0;

    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] < keptEnd) {   // overlap, remove
            removals++;
        } else {                           // fits, keep
            keptEnd = intervals[i][1];
        }
    }
    return removals;
}

int main() {
    vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    cout << eraseOverlapIntervals(intervals) << endl;
    return 0;
}

1

import java.util.Arrays;

public class NonOverlapping {
    public static int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // sort by end

        int keptEnd = intervals[0][1];
        int removals = 0;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < keptEnd) {   // overlap, remove
                removals++;
            } else {                           // fits, keep
                keptEnd = intervals[i][1];
            }
        }
        return removals;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(eraseOverlapIntervals(intervals));
    }
}

1

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda block: block[1])  # sort by end
    kept_end = intervals[0][1]
    removals = 0

    for start, end in intervals[1:]:
        if start < kept_end:        # overlaps the kept block
            removals += 1           # so remove this one
        else:
            kept_end = end          # it fits, keep it
    return removals


intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
print(erase_overlap_intervals(intervals))

1

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]); // sort by end
  let keptEnd = intervals[0][1];
  let removals = 0;

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < keptEnd) {   // overlap, remove
      removals++;
    } else {                           // fits, keep
      keptEnd = intervals[i][1];
    }
  }
  return removals;
}

const intervals = [[1, 2], [2, 3], [3, 4], [1, 3]];
console.log(eraseOverlapIntervals(intervals));

1

Now let us walk through the Python version line by line and see why each part is written this way.

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda block: block[1])
    kept_end = intervals[0][1]
    removals = 0

We sort by block[1], the end of each block. Sorting by end is the heart of the greedy idea. The block that ends earliest leaves the most room, so we keep it first. We store its end in kept_end. That is the wall the next blocks must clear.

    for start, end in intervals[1:]:
        if start < kept_end:
            removals += 1

We loop from the second block. The check start < kept_end reads as “this block starts before the kept block ends.” So they clash. We must remove one of them. We already kept the one that ends earlier, so we drop this new one. We add one to removals and we do not touch kept_end, because the kept block is still the best wall.

        else:
            kept_end = end
    return removals

If the start is not before kept_end, this block fits cleanly after the kept one. So we keep it and move the wall to its end. At the end removals holds the fewest deletions needed.

⏱️ Time and Space Complexity

The brute force checks every subset, so it is exponential and only fine for toy inputs. The greedy sorts by end in O(n log n), then sweeps in O(n). The sort dominates, so the total is O(n log n). Space is O(1) beyond the input, since we only track one end value and one counter. The real lesson is that sorting by end turns a hard removal problem into a simple count.

🧩 Key Takeaways

• ✅ We delete the fewest blocks, which is the same as keeping the most.
• ✅ Sort by end, because a block that ends early leaves more room for others.
• ✅ Keep one wall, the end of the last kept block.
• ✅ If a block starts before the wall, it clashes, so remove it and count it.
• ✅ This greedy runs in O(n log n) time and uses almost no extra space.

🚀 What’s Next?

• Merge Intervals
• Meeting Rooms