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
- Think about scheduling. If you want to attend as many non-overlapping meetings as possible, which meeting should you pick first?
- Sort by end time, then greedily select the intervals that start after the last chosen end. That choice is optimal.
- Once you know how many you can keep, the number to remove is the total minus that count.
Greedy by end time approach
- Sort the intervals by their
endin ascending order. - Initialize:
countKept = 0lastEnd = -∞
- 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.
- If
- 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
Java code
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 == lastEndas 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).
Related problems
-
Two sorted interval lists meet in LeetCode 986. Interval List Intersections, which sweeps both lists with one pointer each.
-
The weighted version of this exact question is LeetCode 1235. Maximum Profit in Job Scheduling, where greedy selection no longer suffices and you add dynamic programming.
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.

GET YOUR FREE
Coding Questions Catalog

$98

$98

$197