Skip to content

Volume ITechnology

4.27.3 — Non-overlapping Intervals ​

LeetCode 435 · Medium

The problem ​

Return the minimum number of intervals to remove so that the rest do not overlap.

Restating the Problem: You are given a collection of intervals. Some of them overlap, creating conflicts. You want to find the absolute minimum number of intervals you need to throw away so that the remaining intervals have zero overlaps.

  • Constraints to note: The array length is up to 10^5, meaning an O(n^2) approach will time out. We need an O(n \log n) sorting-based solution.
  • Edge cases: No intervals might overlap (return 0). All intervals might overlap each other perfectly (keep exactly 1, remove the rest).
[[1,2],[2,3],[3,4],[1,3]]   →  1     (remove [1,3])
[[1,2],[1,2],[1,2]]         →  2
[[1,2],[2,3]]               →  0     (touching is not overlapping here)

The brute force, and where it wastes work ​

The naive approach is to consider every possible subset of the given intervals. For a set of n intervals, there are 2^n possible subsets. For each subset, you check if any intervals overlap. Among all valid non-overlapping subsets, you pick the one with the largest number of intervals. This O(n \cdot 2^n) approach is hopelessly slow for anything beyond very small inputs.

The pattern ​

Turn it round: removing the fewest is the same as keeping the most. So the question becomes what is the largest set of non-overlapping intervals I can keep? — and the answer is n minus that.

That is the activity selection problem, and it has a famous greedy:

Sort by end time, and always keep the interval that finishes earliest among those that still fit.

Why sort by end, not by start ​

This is the question, so here is the proof.

Finishing earliest leaves the most room for everything after it.

Formally, an exchange argument. Suppose some optimal solution does not include the interval that finishes earliest, call it x. Take the first interval in that solution, call it y. Since x finishes no later than y, swapping y for x cannot create a conflict with anything later — everything that fitted after y also fits after x. So there is an optimal solution containing x, and greedy is safe.

Sorting by start fails, and here is why. A very long interval that starts first would be taken, and it would block everything else. With [[1,100],[2,3],[4,5]], sorting by start keeps only [1,100], while sorting by end keeps two.

Sorting by length also fails. [[1,10],[9,12],[11,20]] — the shortest is [9,12], and taking it blocks both others, whereas keeping [1,10] and [11,20] gives two.

Having both counterexamples ready is a strong way to answer "why end time".

The solution ​

python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])           # (1) sort by END

        kept = 0  # (2)
        last_end = float('-inf')  # (3)

        for start, end in intervals:  # (4)
            if start >= last_end:                     # (5) no overlap with what we kept
                kept += 1  # (6)
                last_end = end

        return len(intervals) - kept  # (7)
ts
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);  // (1)

  let kept = 0, lastEnd = -Infinity;  // (2)

  for (const [start, end] of intervals) {  // (4)
    if (start >= lastEnd) {  // (5)
      kept++;  // (6)
      lastEnd = end;
    }
  }

  return intervals.length - kept;  // (7)
}

Line by line ​

Removing the fewest intervals is the same as keeping the most intervals that do not overlap.

(1) Sort by end. The interval that ends first leaves the most room for everything after it, so it is always a safe one to keep.

(2) How many we keep, and

(3) where the last kept interval ends. Minus infinity means nothing is kept yet, so the first interval always fits.

(4) Look at each interval, in order of their ends.

(5) It starts at or after the last kept one ends, so it does not overlap. Here touching is allowed: [1, 2] and [2, 3] do not overlap in this problem.

(6) Keep it, and its end becomes the new limit.

(7) Everything not kept must be removed.

start >= last_end uses >=, because touching intervals do not overlap in this problem — [1,2] and [2,3] can both be kept. Compare 4.27.2 Merge Intervals, where touching intervals do merge and the comparison is <=. Two adjacent problems, opposite conventions — this is exactly why you ask.

last_end starts at negative infinity, so the first interval is always kept.

Code Walkthrough:

  • Sorting: We sort the intervals by their end times. This is the greedy choice that guarantees we leave the maximum possible room for subsequent intervals.
  • Initialization: We keep a counter kept = 0 and track the last_end of the interval we decided to keep (initialized to negative infinity).
  • Iteration: We loop through each start and end in the sorted intervals.
  • Overlap Check (start >= last_end): If the current interval's start is greater than or equal to our last_end, it means it doesn't conflict with the last interval we kept. We keep this new interval, increment kept, and update last_end to its end.
  • Return: The number of intervals we must remove is the total number of intervals minus the number we kept.

Counting kept intervals and subtracting is cleaner than counting removals, because the greedy naturally decides what to keep.

Trace ​

[[1,2],[2,3],[3,4],[1,3]] sorted by end: [[1,2],[1,3],[2,3],[3,4]].

intervallast_endkeep?kept
[1,2]−∞yes1, end 2
[1,3]21 < 2 → no1
[2,3]22 ≥ 2 → yes2, end 3
[3,4]33 ≥ 3 → yes3, end 4

Kept 3, removed 4 − 3 = 1 ✓.

Edge cases ​

  • No overlaps. Every interval is kept, so 0 are removed.
  • All intervals identical. One is kept, the rest are removed.
  • Touching intervals. Both are kept, because touching is not overlapping here.

Complexity ​

O(n \log n) time from the sort, O(1) extra space.

  • Time Complexity: O(n \log n). The time is completely dominated by the sorting step. The greedy linear scan takes O(n) time.
  • Space Complexity: O(1) extra space (excluding the space required by the sorting algorithm itself), because we only use a few integer variables (kept, last_end).

The other interval greedy ​

The mirror problem — Minimum Number of Arrows to Burst Balloons (LeetCode 452) — is the same algorithm with the answer read differently.

You want the fewest points that touch every interval. Sort by end, shoot an arrow at the end of the first interval, skip everything it hits, and repeat. The number of arrows equals the number of intervals you would have "kept" here.

They are the same computation: the count of intervals kept is both the largest non-overlapping set and the fewest points needed to stab all of them. That duality is a nice thing to notice, and it is why the two problems have identical code.

Watch one detail there: touching balloons are burst by the same arrow, so the comparison flips to >.

Where this goes next ​

  • Merge Intervals — sort by start instead. 4.27.2.
  • Maximum Length of Pair Chain — identical to this problem, counting kept pairs directly.
  • Minimum Arrows to Burst Balloons — above.
  • Job Scheduling with profits — when intervals have values, greedy fails and it becomes DP with binary search, O(n \log n). That is the boundary: unweighted activity selection is greedy; weighted is DP. Naming it shows you know where the greedy stops working.

What the interviewer will push on ​

"Why sort by end?" The exchange argument, plus the [[1,100],[2,3],[4,5]] counterexample against sorting by start.

"Why not sort by length?" [[1,10],[9,12],[11,20]].

"Does touching count as overlapping?" Not here — hence >=. And it is the opposite convention to Merge Intervals, so ask on every interval problem.

"Why count kept rather than removed?" The greedy decides what to keep; removals are the leftover.

"What if intervals had weights?" Greedy breaks; it becomes DP with binary search.

One thing to volunteer: give the exchange argument before the code. This is the chapter where greedy proofs are short and expected, and one sentence of justification separates a correct solution from a lucky one.

Next: 4.27.4 Meeting Rooms — the simplest interval question there is, and the warm-up for the one after it.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet