Non-overlapping Intervals (LeetCode 435)
You have an array of intervals intervals, each entry [start_i, end_i]. Find the fewest intervals you'd need to delete so that whatever remains has no two intervals overlapping, and return that count.
Touching at a single boundary point does not count as overlapping -- [1, 2] and [2, 3] are considered non-overlapping.
Worked Examples
intervals = [[1,2],[2,3],[3,4],[1,3]]1intervals = [[1,2],[1,2],[1,2]]2intervals = [[1,2],[2,3]]0⚖️Formal Constraints & Bounds
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= start_i < end_i <= 5 * 104
Core Insight
Greedy choice by earliest finish time is mathematically guaranteed to maximize non-overlapping capacity.
Real-World Scenario & Production Applications
Conference room scheduling optimization, telescope observation window allocation.
Step-by-Step Execution Trace Table
| Interval (Sorted by End) | prev_end | Conflict (start < prev_end)? | Action | Removals |
|---|---|---|---|---|
| [1, 2] | 2 | - | Keep (initial) | 0 |
| [2, 3] | 2 | 2 < 2 -> No | Keep, prev_end=3 | 0 |
| [1, 3] | 3 | 1 < 3 -> YES | Remove [1,3] | 1 |
| [3, 4] | 3 | 3 < 3 -> No | Keep, prev_end=4 | 1 |
| 1 | intervals.sort(key=lambda iv: iv[1]) |
| 2 | removed_count = 0 |
| 3 | prev_end = intervals[0][1] |
| 4 | for start, end in intervals[1:]: |
| 5 | if start < prev_end: |
| 6 | removed_count += 1 |
| 7 | else: |
| 8 | prev_end = end |
| 9 | return removed_count |
Conceptual Narrative
Removing the minimum number of intervals to eliminate overlaps is mathematically dual to selecting the maximum number of mutually compatible intervals via greedy earliest finish time.
🧭 Conceptual Foundation & Pattern Intuition
Given a collection of intervals, we want to find the minimum number of intervals to remove so that the remaining intervals do not overlap. Invert the problem: This is the classic Interval Scheduling / Activity Selection Problem, famously proven solvable via a Greedy Algorithm:
- Sort intervals by their end time (
intervals.sort(key=lambda iv: iv[1])). - Always select the interval that finishes earliest. Why? Because finishing as early as possible leaves the maximal remaining timeline available for subsequent intervals!
- Keep the first (earliest-finishing) interval and set
prev_endto its end. For each subsequent interval:- If
start >= prev_end, it does not conflict! Accept it and updateprev_end = end. - If
start < prev_end, it conflicts with our greedily optimal selection. It must be removed (removed_count += 1).
- If
🎭 The Analogy: Booking a Single Stage at a Music Festival
Imagine booking indie bands on a single festival stage from noon to midnight. To pack as many bands into the day as possible, you don't book the band that starts earliest (they might play an 8-hour marathon set and block the whole afternoon). Instead, you always book the band that finishes earliest. The sooner the stage is free, the more time you preserve for future bands to perform. Every band whose set overlaps with the currently performing band must be declined.
🔑 Why It Works
Sorting by end time guarantees that every greedy retention decision is globally optimal, eliminating the need for dynamic programming and resolving the problem in time and auxiliary space.
Sorting by start time instead of end time: Sorting by start time fails on long spans that start early (e.g.
[1, 100]and[2, 3]); sorting by end time is mathematically proven optimal.Touching boundaries are compatible: Intervals touching at borders (e.g.
[1, 2]and[2, 3]) do NOT overlap per problem specification. Condition isstart >= prev_end.Returning retained count instead of removed count: Problem asks for removals (
len(intervals) - retainedor counting increments when overlapping).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The fewest intervals you'd need to delete so that whatever remains has no two intervals overlapping": deleting the fewest is the same as keeping the most.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: an interval with start < prev_end overlaps the last kept one, so it is removed; otherwise it is kept and prev_end moves to its end.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Sorting by start and keeping whichever interval comes first: on
[[1,100],[2,3],[3,4]]the long[1,100]is kept and both short ones are removed (2 instead of 1).Looping over all of
intervalsinstead ofintervals[1:]: the first interval is compared with its own end,start < prev_endholds, and it is counted as a removal.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Interval Scheduling. Removing the fewest intervals is the same as keeping the most, so I sort by end time and keep an interval whenever it starts at or after the end of the last one I kept, prev_end; everything else counts as removed. Keeping the interval that finishes first is safe: any best answer can swap its first interval for this one without losing room for the rest. The trap is sorting by start and keeping whoever comes first, because one long early interval then blocks several short ones: on [[1,100],[2,3],[3,4]] that removes two intervals when one is enough. Sorting is
O(N log N)time, and the sort's keys takeO(N)space; beyond that I only keep prev_end and the count."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: intervals.sort(key=lambda iv: iv[1]) takes O(N log N). The loop over intervals[1:] does O(1) work per interval: if start < prev_end, add one to removed_count; else move prev_end. The sort dominates.
O(N) Auxiliary
Look at memory allocations: the sort with a key builds N keys and Python's sort may use up to O(N) more, so O(N). Beyond the sort, only prev_end and removed_count: O(1). (intervals[1:] also copies N - 1 references; range(1, len(intervals)) would avoid it.)
T(N) = O(N log N) + O(N) = O(N log N)
Derivation Progression
O(N log N) key=lambda x: x[1]
Orders by earliest deadline to maximize remaining space for subsequent intervals.
if start < prev_end: removed_count += 1 else prev_end = end
Removes the interval that overlaps the last kept one, in O(1).
O(N) linear pass
Provably minimal removals.
Variable Definitions
Total number of interval requests
Memory Architecture & Bounds
O(1) Iterative
O(N) sort keys and buffer; O(1) (prev_end) beyond the sort
O(1) Minimum removals integer
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum number of intervals to remove to make the rest non-overlapping". Classic Interval Scheduling Maximization Problem (ISMP): minimizing removals is the same as maximizing the number of compatible intervals kept. At production scale it is admission control: accept the most bookings on one resource.
. Time budget is sorting followed by an greedy pass.
When requests arrive online in start order (bookings as they come in), the end-sorted greedy is not available: accepting greedily in arrival order can be far from the best. Batch the requests and sort by end, or accept that an online policy gives a weaker guarantee.
Non-overlapping Intervals (LeetCode 435)
You have an array of intervals intervals, each entry [start_i, end_i]. Find the fewest intervals you'd need to delete so that whatever remains has no two intervals overlapping, and return that count.
Touching at a single boundary point does not count as overlapping -- [1, 2] and [2, 3] are considered non-overlapping.
Worked Examples
intervals = [[1,2],[2,3],[3,4],[1,3]]1intervals = [[1,2],[1,2],[1,2]]2intervals = [[1,2],[2,3]]0⚖️Formal Constraints & Bounds
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= start_i < end_i <= 5 * 104
Core Insight
Greedy choice by earliest finish time is mathematically guaranteed to maximize non-overlapping capacity.
Real-World Scenario & Production Applications
Conference room scheduling optimization, telescope observation window allocation.
Step-by-Step Execution Trace Table
| Interval (Sorted by End) | prev_end | Conflict (start < prev_end)? | Action | Removals |
|---|---|---|---|---|
| [1, 2] | 2 | - | Keep (initial) | 0 |
| [2, 3] | 2 | 2 < 2 -> No | Keep, prev_end=3 | 0 |
| [1, 3] | 3 | 1 < 3 -> YES | Remove [1,3] | 1 |
| [3, 4] | 3 | 3 < 3 -> No | Keep, prev_end=4 | 1 |
| 1 | intervals.sort(key=lambda iv: iv[1]) |
| 2 | removed_count = 0 |
| 3 | prev_end = intervals[0][1] |
| 4 | for start, end in intervals[1:]: |
| 5 | if start < prev_end: |
| 6 | removed_count += 1 |
| 7 | else: |
| 8 | prev_end = end |
| 9 | return removed_count |
Conceptual Narrative
Removing the minimum number of intervals to eliminate overlaps is mathematically dual to selecting the maximum number of mutually compatible intervals via greedy earliest finish time.
🧭 Conceptual Foundation & Pattern Intuition
Given a collection of intervals, we want to find the minimum number of intervals to remove so that the remaining intervals do not overlap. Invert the problem: This is the classic Interval Scheduling / Activity Selection Problem, famously proven solvable via a Greedy Algorithm:
- Sort intervals by their end time (
intervals.sort(key=lambda iv: iv[1])). - Always select the interval that finishes earliest. Why? Because finishing as early as possible leaves the maximal remaining timeline available for subsequent intervals!
- Keep the first (earliest-finishing) interval and set
prev_endto its end. For each subsequent interval:- If
start >= prev_end, it does not conflict! Accept it and updateprev_end = end. - If
start < prev_end, it conflicts with our greedily optimal selection. It must be removed (removed_count += 1).
- If
🎭 The Analogy: Booking a Single Stage at a Music Festival
Imagine booking indie bands on a single festival stage from noon to midnight. To pack as many bands into the day as possible, you don't book the band that starts earliest (they might play an 8-hour marathon set and block the whole afternoon). Instead, you always book the band that finishes earliest. The sooner the stage is free, the more time you preserve for future bands to perform. Every band whose set overlaps with the currently performing band must be declined.
🔑 Why It Works
Sorting by end time guarantees that every greedy retention decision is globally optimal, eliminating the need for dynamic programming and resolving the problem in time and auxiliary space.
Sorting by start time instead of end time: Sorting by start time fails on long spans that start early (e.g.
[1, 100]and[2, 3]); sorting by end time is mathematically proven optimal.Touching boundaries are compatible: Intervals touching at borders (e.g.
[1, 2]and[2, 3]) do NOT overlap per problem specification. Condition isstart >= prev_end.Returning retained count instead of removed count: Problem asks for removals (
len(intervals) - retainedor counting increments when overlapping).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The fewest intervals you'd need to delete so that whatever remains has no two intervals overlapping": deleting the fewest is the same as keeping the most.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: an interval with start < prev_end overlaps the last kept one, so it is removed; otherwise it is kept and prev_end moves to its end.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Sorting by start and keeping whichever interval comes first: on
[[1,100],[2,3],[3,4]]the long[1,100]is kept and both short ones are removed (2 instead of 1).Looping over all of
intervalsinstead ofintervals[1:]: the first interval is compared with its own end,start < prev_endholds, and it is counted as a removal.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Interval Scheduling. Removing the fewest intervals is the same as keeping the most, so I sort by end time and keep an interval whenever it starts at or after the end of the last one I kept, prev_end; everything else counts as removed. Keeping the interval that finishes first is safe: any best answer can swap its first interval for this one without losing room for the rest. The trap is sorting by start and keeping whoever comes first, because one long early interval then blocks several short ones: on [[1,100],[2,3],[3,4]] that removes two intervals when one is enough. Sorting is
O(N log N)time, and the sort's keys takeO(N)space; beyond that I only keep prev_end and the count."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: intervals.sort(key=lambda iv: iv[1]) takes O(N log N). The loop over intervals[1:] does O(1) work per interval: if start < prev_end, add one to removed_count; else move prev_end. The sort dominates.
O(N) Auxiliary
Look at memory allocations: the sort with a key builds N keys and Python's sort may use up to O(N) more, so O(N). Beyond the sort, only prev_end and removed_count: O(1). (intervals[1:] also copies N - 1 references; range(1, len(intervals)) would avoid it.)
T(N) = O(N log N) + O(N) = O(N log N)
Derivation Progression
O(N log N) key=lambda x: x[1]
Orders by earliest deadline to maximize remaining space for subsequent intervals.
if start < prev_end: removed_count += 1 else prev_end = end
Removes the interval that overlaps the last kept one, in O(1).
O(N) linear pass
Provably minimal removals.
Variable Definitions
Total number of interval requests
Memory Architecture & Bounds
O(1) Iterative
O(N) sort keys and buffer; O(1) (prev_end) beyond the sort
O(1) Minimum removals integer
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum number of intervals to remove to make the rest non-overlapping". Classic Interval Scheduling Maximization Problem (ISMP): minimizing removals is the same as maximizing the number of compatible intervals kept. At production scale it is admission control: accept the most bookings on one resource.
. Time budget is sorting followed by an greedy pass.
When requests arrive online in start order (bookings as they come in), the end-sorted greedy is not available: accepting greedily in arrival order can be far from the best. Batch the requests and sort by end, or accept that an online policy gives a weaker guarantee.