435. Non-overlapping Intervals

At a Glance

Topic: greedy
Pattern: Greedy on intervals (pick earliest ending)
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Bloomberg, Apple
Frequency: High
LeetCode: 435

Problem (one-liner)

Given intervals [start, end], return the minimum number of intervals you must remove so that the rest are pairwise non-overlapping (strictly, typically end_i <= start_j for ordering).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Minimum removals” / max non-overlap subset
Sort by end time ascending; greedy keep interval if its start ≥ last kept end
Classic “activity selection”

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DP — O(n²) time.
Greedy by earliest finish — O(n log n) time / O(1) extra (besides sort). <- pick this in interview.

Optimal Solution

Go

package main

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) <= 1 {
		return 0
	}
	sort.Slice(intervals, func(left int, right int) bool {
		return intervals[left][1] < intervals[right][1]
	})
	kept := 0
	lastEnd := intervals[0][1]
	for index := 1; index < len(intervals); index++ {
		start := intervals[index][0]
		end := intervals[index][1]
		if start >= lastEnd {
			kept++
			lastEnd = end
		}
	}
	return len(intervals) - (kept + 1)
}

JavaScript

function eraseOverlapIntervals(intervals) {
	if (intervals.length <= 1) return 0;
	const sorted = [...intervals].sort((left, right) => left[1] - right[1]);
	let kept = 0;
	let lastEnd = sorted[0][1];
	for (let index = 1; index < sorted.length; index++) {
		const [start, end] = sorted[index];
		if (start >= lastEnd) {
			kept++;
			lastEnd = end;
		}
	}
	return intervals.length - (kept + 1);
}