Non Overlapping Intervals

MEDIUM✓ CHIP-TIMEDLC #435 — FULL STATEMENT ↗

The drill: A set of intervals has some pairwise overlaps. Remove the fewest possible so that what remains never overlaps — touching at a shared endpoint is fine.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A collection of intervals, each described by a start and an end, sits together on one line — and some of them cross each other in time. The task is to strip away as few of them as possible so that whatever remains never overlaps.

Two intervals overlap only when one genuinely begins before the other ends; sharing a single endpoint, where one interval ends exactly where the next begins, counts as clean and never forces a removal.

The number handed back is just a count — how many intervals had to go — not the intervals themselves. The input list's own order carries no meaning; only the raw start and end pairs matter.

EX 01

intervals = [[1, 3], [3, 6], [2, 4]]

→ 1

ONE OVERLAP IN A CHAIN OF THREE

EX 02

intervals = [[1, 2], [3, 4], [5, 6]]

→ 0

ALREADY NON-OVERLAPPING

EX 03

intervals = [[1, 4], [1, 4], [1, 4]]

→ 2

THREE IDENTICAL INTERVALS, KEEP ONE

dozens to low thousands of intervals in a single call
start and end values can be any integers, including negative ones
an interval's end is never before its own start
touching endpoints (one end equal to the next start) never count as overlap

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Removing intervals to kill overlaps is really about choosing which ones to KEEP — and the ones kept should leave as much room as possible for the rest. What quantity, sorted first, maximizes remaining room?

HINT 2 THE STRUCTURE

Sort by end time. The interval that finishes earliest always leaves the most room for whatever comes after it, so it is never wrong to keep it.

HINT 3 ONE STEP FROM THE ANSWER

Greedily keep the earliest-ending interval that still starts at or after the last kept interval's end; every interval that starts before that is an overlap you must discard — count those discards.

COACH'S BOARD — THE PATTERN, STEP BY STEP

GREEDY BY END TIMEPATTERN · GREEDY — SORT BY ENDintervals = [[1,3],[3,6],[2,4]]

[1,3]

[2,4]

[3,6]

PREV END / REMOVED

prev_end → –

removed → 0

STEP 1

Sort by end time: [1,3], [2,4], [3,6]. Keep whichever interval finishes earliest — it always leaves the most room.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/non-overlapping-intervals.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        ivs = sorted(intervals, key=lambda iv: iv[1])
        removed = 0
        prev_end = ivs[0][1]
        for start, end in ivs[1:]:
            if start < prev_end:
                removed += 1
            else:
                prev_end = end
        return removed

TIME O(N LOG N)SPACE O(1)PYTHON · RACE PACE · 13 LN

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        ivs = sorted(intervals, key=lambda iv: iv[0])
        n = len(ivs)
        dp = [1] * n  # dp[i] = largest non-overlapping subset ending at interval i
        for i in range(n):
            for j in range(i):
                if ivs[j][1] <= ivs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return n - max(dp)

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int[][] ivs = intervals.clone();
        Arrays.sort(ivs, (a, b) -> Integer.compare(a[1], b[1]));
        int removed = 0;
        int prevEnd = ivs[0][1];
        for (int i = 1; i < ivs.length; i++) {
            if (ivs[i][0] < prevEnd) {
                removed++;
            } else {
                prevEnd = ivs[i][1];
            }
        }
        return removed;
    }
}

TIME O(N LOG N)SPACE O(1)JAVA · RACE PACE · 17 LN

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int[][] ivs = intervals.clone();
        Arrays.sort(ivs, (a, b) -> Integer.compare(a[0], b[0]));
        int n = ivs.length;
        int[] dp = new int[n];
        int best = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (ivs[j][1] <= ivs[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return n - best;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 20 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED