435. Non-overlapping Intervals - Detailed Explanation

Problem statement

You are given an array of intervals intervals where each interval is a pair [start, end). Your goal is to remove the minimum number of intervals so that the remaining intervals are non-overlapping. Return that minimum number of intervals to remove.

You can ask the same question from the other side: what is the maximum number of non-overlapping intervals you can keep? The answer is then total_intervals - max_kept.

This question belongs to the Merge Intervals pattern, the family of techniques that sort intervals by one endpoint and then sweep through them once, comparing each interval only against the one it follows. Sorting is what makes a single comparison enough. The pattern covers merging, inserting, and interval conflicts alike, and it is one of the recurring coding interview patterns. This particular question also appears on the Blind 75 list.

Examples

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: Remove [1,3], leaving [[1,2],[2,3],[3,4]] which are non-overlapping.

Example 2

Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You must remove two of them, leaving only one interval.

Example 3

Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: Already non-overlapping.

Constraints

  • 1 ≤ intervals.length ≤ 10⁵
  • intervals[i].length == 2
  • -10⁵ ≤ intervals[i][0] < intervals[i][1] ≤ 10⁵

Hints

  1. Think about scheduling. If you want to attend as many non-overlapping meetings as possible, which meeting should you pick first?
  2. Sort by end time, then greedily select the intervals that start after the last chosen end. That choice is optimal.
  3. Once you know how many you can keep, the number to remove is the total minus that count.

Greedy by end time approach

  1. Sort the intervals by their end in ascending order.
  2. Initialize:
    • countKept = 0
    • lastEnd = -∞
  3. Iterate over each interval [s, e] in sorted order:
    • If s ≥ lastEnd, you can keep this interval:
      • countKept++
      • lastEnd = e
    • Otherwise, you must remove it, so skip the increment.
  4. The answer, meaning the minimum number of removals, is:
    intervals.length - countKept

Why it works

  • Picking the interval that finishes earliest leaves the widest remaining window for the intervals that follow.
  • This is the classic interval scheduling algorithm, and it is proven optimal.

Step by step walkthrough (example 1)

intervals = [[1,2],[2,3],[3,4],[1,3]] Sorted by end -> [[1,2],[2,3],[1,3],[3,4]] lastEnd = -inf, countKept = 0 [1,2]: 1 >= -inf -> keep -> countKept=1, lastEnd=2 [2,3]: 2 >= 2 -> keep -> countKept=2, lastEnd=3 [1,3]: 1 < 3 -> overlaps -> remove [3,4]: 3 >= 3 -> keep -> countKept=3, lastEnd=4 Kept = 3 of 4 -> removals = 4 - 3 = 1

Complexity analysis

  • Time:
    • Sorting takes O(n log n), where n is the number of intervals.
    • The single linear scan takes O(n).
    • Total: O(n log n).
  • Space:
    • O(log n) or O(n), depending on the sort implementation.
    • O(1) extra for the pointers and counters.

Python code

Python3
Python3

. . . .

Java code

Java
Java

. . . .

Common mistakes

  • Sorting by start time instead of end time leads to choices that keep fewer intervals.
  • Detecting overlaps with nested loops costs O(n²), which times out at the upper constraint.
  • Your overlap test can be off by one. It must treat s == lastEnd as non-overlapping.

Edge cases

  • All intervals identical, where you must remove all but one.
  • Intervals that only touch, such as [a,b] and [b,c], which are not overlapping.
  • A very large n, which pushes both the sort and the scan, so keep the solution at O(n log n).

Granted, each of these needs its own insight, but the sort first move is shared. The whole interval family is taught together in Grokking the Coding Interview.

TAGS
Coding Interview Questions
Coding Interview
CONTRIBUTOR
Arslan Ahmad
Arslan Ahmad
ex-FAANG engineering manager and author or Grokking series.

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
What is indexing in SQL?
What Is the Zoom Interview Process Like? (Round by Round)
Zoom's software engineer loop: recruiter screen, live coding screen, and a virtual onsite with coding, system design, and behavioral rounds.
What is your weak point?
What is the success rate of the Meta interview?
What if you don't understand a coding question an interviewer asks?
What is the key concept of cloud computing?
Related Courses
New
Grokking Agentic Design Patterns course cover
Grokking Agentic Design Patterns
Design agents that act safely, recover from failure, and justify their cost.
4.9
(561 learners)
Discounted price for Your Region

$98

New
Grokking the AI System Design Interview course cover
Grokking the AI System Design Interview
Learn to design AI systems the way interviewers expect: classic ML products, LLM and RAG architectures, and agentic systems, all through the lens of the system design interview.
4.6
(3,192 learners)
Discounted price for Your Region

$98

Grokking the Coding Interview: Patterns for Coding Questions course cover
Grokking the Coding Interview: Patterns for Coding Questions
The 24 essential patterns behind every coding interview question. Available in Java, Python, JavaScript, C++, C#, and Go. The most comprehensive coding interview course with 543 lessons. A smarter alternative to grinding LeetCode.
4.6
Discounted price for Your Region

$197

Design Gurus logo
One-Stop Portal For Tech Interviews.
About Us
Our Team
Careers
Partners
Contact Us
Become Affiliate
Copyright © 2026 Design Gurus, LLC. All rights reserved.