Non-Overlapping Intervals LeetCode: Greedy Interval Scheduling

Non-overlapping intervals leetcode problem #435 is the textbook greedy interval scheduling question. Given a collection of intervals, find the minimum number of intervals you need to remove so the remaining intervals do not overlap. It sounds like a hard optimization problem, but the greedy approach solves it cleanly in O(n log n) time.

This problem is identical to the activity selection problem taught in every algorithms course. The key insight is deceptively simple: sort by end time, greedily keep non-overlapping intervals, and count the removals. Once you see why this works, you can apply the same logic to Meeting Rooms, Merge Intervals, and other interval scheduling questions.

In this walkthrough, we will break down the greedy insight, explain why sorting by end time matters, trace through a visual example, and cover the edge cases that trip people up in interviews.

You are given an array of intervals where each interval is a pair [start, end]. Your goal is to return the minimum number of intervals you must remove so that the remaining intervals are all non-overlapping. Two intervals overlap if one starts before the other ends.

For example, given [[1,2],[2,3],[3,4],[1,3]], the answer is 1 — remove [1,3] and the remaining intervals [1,2], [2,3], [3,4] do not overlap. Notice that [1,2] and [2,3] share the endpoint 2 but are not considered overlapping because one ends exactly where the other begins.

The brute-force approach would try every possible subset of intervals to find the largest non-overlapping set — that is exponential. The greedy approach flips the problem: instead of deciding which intervals to remove, figure out the maximum number you can keep. Removals equals total minus kept.

The greedy strategy is straightforward. Sort all intervals by their end time. Initialize a variable to track the end time of the last interval you kept. Walk through the sorted intervals: if the current interval's start is greater than or equal to the last kept end, keep it and update the tracker. Otherwise, skip it — it overlaps.

After one pass, you know the maximum number of non-overlapping intervals. The answer to leetcode 435 is simply total intervals minus the number you kept. This runs in O(n log n) for the sort plus O(n) for the scan, giving O(n log n) overall with O(1) extra space.

Why does greedy work here? At every step, choosing the interval with the earliest end time leaves the most room for future intervals. This is a provably optimal strategy — no other selection can fit more intervals. The greedy choice property and optimal substructure guarantee correctness.

Sorting by start time is the most common mistake on this problem. If you sort by start time, you might greedily pick an interval that starts early but extends far into the future, blocking many shorter intervals that could have fit. Sorting by end time avoids this trap entirely.

Consider intervals [1,10], [2,3], [3,5], [5,7]. Sorted by start time, you would pick [1,10] first — and that overlaps with everything else, forcing you to remove three intervals. Sorted by end time, you pick [2,3], then [3,5], then [5,7] — removing only [1,10]. The end-time sort naturally favors shorter intervals that leave more room.

This is the mathematical foundation of the activity selection proof. The interval with the earliest end time is always safe to include because it constrains the fewest future choices. Every algorithms textbook proves this with an exchange argument: swapping any other interval for the one with the earliest end time never makes the solution worse.

Let us trace through the example [[1,2],[2,3],[3,4],[1,3]] step by step. First, sort by end time: [1,2], [2,3], [1,3], [3,4]. Notice [1,3] comes after [2,3] because its end time (3) ties but the order among ties does not matter.

Start with lastEnd = -infinity. Interval [1,2]: start 1 >= -infinity, so keep it. Update lastEnd = 2. Kept = 1. Interval [2,3]: start 2 >= 2, so keep it. Update lastEnd = 3. Kept = 2. Interval [1,3]: start 1 < 3, so skip it (overlaps). Kept still 2. Interval [3,4]: start 3 >= 3, so keep it. Update lastEnd = 4. Kept = 3.

We kept 3 out of 4 intervals, so removals = 4 - 3 = 1. The removed interval is [1,3], which is exactly the one that overlapped. The greedy algorithm found the optimal answer in a single pass after sorting.

Several edge cases appear frequently in interviews for the minimum interval removals problem. Understanding them shows your interviewer you have thought beyond the happy path.

When no intervals overlap at all, the answer is 0 — you remove nothing. When every interval is identical (like [[1,3],[1,3],[1,3]]), you keep exactly one and remove n-1. When all intervals overlap with each other, the answer is also n-1 because you can only keep the one with the earliest end time.

Touching endpoints are the trickiest edge case. The problem defines [1,2] and [2,3] as non-overlapping because they share only a single point. Your comparison must use start >= lastEnd (greater than or equal), not start > lastEnd. Getting this comparison wrong is one of the most common bugs on this problem.

LeetCode 435 is more than just one problem — it is the foundation for an entire family of interval questions. The greedy interval scheduling pattern shows up in Meeting Rooms II (LeetCode 253), Merge Intervals (LeetCode 56), Insert Interval (LeetCode 57), and Minimum Number of Arrows to Burst Balloons (LeetCode 452).

The core lesson is that greedy interval scheduling always starts with sorting by end time. Once you internalize this, the variations become straightforward. Meeting Rooms asks if any intervals overlap (sort and check adjacent pairs). Merge Intervals asks you to combine overlapping intervals (sort by start, merge greedily). Non-overlapping Intervals asks for minimum removals (sort by end, count kept).

Drilling this pattern with YeetCode flashcards helps you instantly recognize interval problems in interviews. Instead of re-deriving the approach under pressure, you will know to sort by end time, scan once, and count. That kind of automatic pattern recognition is what separates prepared candidates from those who struggle with time.