Free lesson · DSA Mastery - Interview Prep, End to End
Non-overlapping Intervals
Non-overlapping Intervals
Non-overlapping Intervals opens the large Greedy Intervals sub-group with the canonical earliest-finish greedy: find the minimum number of intervals to remove so the rest are non-overlapping. Sorting by end and repeatedly keeping the interval that finishes earliest (removing any that conflict with the last kept one) maximizes the surviving set - and the count removed is the answer. It is the classic activity-selection greedy that flips the section's sort key from start to end, and the exchange argument behind it justifies the entire greedy sub-group that follows. We present the sort-by-end greedy (canonical) and the sort-by-start DP-style alternative.
The insight: minimizing removals is the same as maximizing the number of non-overlapping intervals you keep. To keep the most, greedily always keep the interval that finishes earliest among those compatible with what you've kept - finishing early leaves the most room for future intervals. Sort by end; track the last kept end; accept an interval only if its start is >= that end (otherwise it overlaps and must be removed). This earliest-finish-first rule is provably optimal by an exchange argument.
The Problem
Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: Remove [1,3]; the rest [[1,2],[2,3],[3,4]] are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: Remove two of the three identical [1,2] intervals.
Constraints:
1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= start_i < end_i <= 5 * 10^4
Approaches Overview
| # | Approach | Time | Space | Verdict |
|---|---|---|---|---|
| 1 | Sort by start + DP (longest non-overlapping chain) | O(n²) or O(n log n) | O(n) | Alternative |
| 2 | Sort by end + earliest-finish greedy | O(n log n) | O(1) | Canonical |
The DP alternative sorts by start and finds the longest non-overlapping chain (like longest increasing subsequence on intervals); removals = total − chain length. The canonical greedy sorts by end and keeps every interval whose start is at or after the last kept end, counting the rest as removals. The greedy is simpler, O(1) space, and provably optimal by the earliest-finish exchange argument - the activity-selection classic.
Approach 1: Sort by Start + DP - Alternative
The Idea
Sort by start. Compute the longest chain of mutually non-overlapping intervals (each next interval starts at or after the previous one's end) - analogous to longest increasing subsequence. The minimum removals equal n minus this longest chain length. An O(n²) DP or an O(n log n) patience-style refinement works, but it's heavier than the greedy.
Complexity
Time: O(n²) naive DP (or O(n log n) optimized). Space: O(n).
Approach 2: Sort by End + Earliest-Finish Greedy - Canonical
The Idea
Sort by end ascending. Track lastEnd, the end of the most recently kept interval (start at −∞). For each interval [s, e]: if s >= lastEnd, it doesn't overlap the last kept one - keep it, set lastEnd = e. Otherwise it overlaps - it must be removed; increment the removal count. The count of removed intervals is the answer.
Logic Flowchart
graph TD
A["sort by end ascending"] --> B["lastEnd = -infinity; removals = 0"]
B --> C["for each [s, e]"]
C --> D{"s >= lastEnd? (no overlap)"}
D -->|Yes keep| E["lastEnd = e"]
D -->|No overlap| F["removals++ (remove this one)"]
E --> C
F --> C
C --> G["return removals"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows the earliest-finish greedy. After sorting by end, each interval is kept if its start is at or after the last kept end, updating that end; otherwise it overlaps and is counted as a removal.
Code
public static int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // by END ascending
int removals = 0;
long lastEnd = Long.MIN_VALUE; // end of last kept interval
for (int[] iv : intervals) {
if (iv[0] >= lastEnd) { // start at/after last kept end → no overlap, keep
lastEnd = iv[1];
} else { // overlaps the last kept interval → must remove
removals++;
}
}
return removals;
}
// Usage:
// eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]) -> 1
This Java code sorts intervals by end, then keeps each interval whose start is at or after the last kept end, updating that end, and counts the rest as removals.
Step-by-Step Walkthrough
A frame-by-frame trace on intervals = [[1,2],[2,3],[3,4],[1,3]]:
graph LR
F0["sort by end: [1,2],[1,3],[2,3],[3,4]"]
F1["[1,2]: 1 >= -inf → keep, lastEnd=2. [1,3]: 1 < 2 → overlap, remove (removals=1)"]
F2["[2,3]: 2 >= 2 → keep, lastEnd=3. [3,4]: 3 >= 3 → keep, lastEnd=4"]
F3["removals = 1"]
F0 --> F1 --> F2 --> F3
style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F1 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
This walkthrough minimizes removals. Sorted by end, one-two is kept, one-three overlaps and is removed, then two-three and three-four are kept, giving one removal.
Result: 1.
Complexity
Time: O(n log n) - sort dominates; the sweep is O(n). Space: O(1) beyond sorting.
Complexity Comparison
| Approach | Time | Space | Key Idea | When to Use |
|---|---|---|---|---|
| Sort by start + DP | O(n²) / O(n log n) | O(n) | Longest non-overlapping chain | When DP framing is clearer |
| Sort by end + greedy | O(n log n) | O(1) | Keep earliest-finishing compatible interval | Canonical |
The greedy is simpler and uses O(1) space. Sorting by end (not start) is the pivotal choice: keeping the earliest-finishing interval leaves maximal room for the rest, which the exchange argument proves optimal. This flips the section's sort key and establishes the template for the greedy sub-group.
Variations & Follow-ups
Why does sorting by end (not start) and keeping earliest-finishing intervals maximize the kept set?
This is the classic activity-selection result. Among all intervals compatible with what you've kept, the one that finishes earliest leaves the largest remaining free space for future intervals - any other choice ends later and can only block as much or more. The exchange argument makes it rigorous: take any optimal solution; its first-kept interval can be swapped for the globally earliest-finishing interval without reducing the count (the earliest-finisher ends no later, so everything compatible with the original is still compatible). Repeating this swap transforms any optimal solution into the greedy one, proving the greedy is optimal. Sorting by end is what surfaces the earliest-finisher at each step; sorting by start does not support this argument (an early-starting interval can end very late and block many others).
Why is minimizing removals equivalent to maximizing the kept non-overlapping set?
Every interval is either kept or removed, so removals = n − kept. Since n is fixed, minimizing removals is exactly maximizing kept. This reframing is what lets the activity-selection greedy apply: instead of reasoning about which to delete (hard to do directly), you reason about which to keep (the well-understood maximum-compatible-set problem) and report the complement. Recognizing that a "minimum deletions to satisfy a property" problem is the dual of a "maximum subset with the property" problem is a broadly useful transformation - it converts a removal problem into a selection problem with a known optimal greedy.
Why does the greedy count removals on the fly instead of building the kept set?
You don't need the actual kept intervals, only how many were removed. So the sweep tracks just lastEnd (the end of the most recently kept interval) and increments a counter whenever an interval overlaps it. An interval overlaps the last kept one exactly when its start is before lastEnd (s < lastEnd); since intervals are sorted by end, the last kept interval has the smallest end among kept-so-far, making it the binding constraint. Keeping an interval updates lastEnd; removing one leaves lastEnd unchanged (you discard the overlapper, not the keeper). This O(1)-state sweep directly yields the removal count without materializing the kept set - the same "running summary" economy as the previous problem's maxEnd.
Why does touching count as non-overlapping here, and how does >= encode it?
The problem explicitly states intervals touching at a point (like [1,2] and [2,3]) are non-overlapping - you can keep both. So an interval is compatible with the last kept one when its start is at or after the last kept end: s >= lastEnd. The >= (not strict >) admits the touching case as a keep. If the problem treated touching as overlap, you'd use strict >. This is the same endpoint-convention decision seen throughout the section, and here it directly affects the answer - using > instead of >= would wrongly remove valid touching intervals and over-count removals. Read the statement's touching rule and match the comparison.
What about edge cases?
- All identical intervals (Example 2): All but one overlap the kept one; remove
n − 1. - Already non-overlapping: Every interval is kept; zero removals.
- Single interval: Kept; zero removals.
- Nested intervals (
[1,10],[2,3]): Sorted by end,[2,3](end 3) comes first and is kept;[1,10]overlaps it and is removed - correctly keeping the one that frees more room. - Touching chain (Example 1's
[1,2],[2,3],[3,4]): All kept via>=.
Common Interview Pitfalls
- Sorting by start instead of end. Breaks the earliest-finish greedy; an early-starting, late-ending interval would be kept and block many others.
- Using strict
>for the keep condition. Wrongly removes touching intervals; use>=when touching is allowed. - Counting kept instead of removed. The answer is removals = total − kept; return the removal count.
- Integer overflow on the sentinel. Initialize
lastEndto a value below all starts (e.g.,Long.MIN_VALUE).
Why This Topic Matters
Non-overlapping Intervals is the canonical earliest-finish greedy (activity selection) and the cornerstone of the greedy sub-group: sort by end, keep the earliest-finishing compatible interval, count the rest as removals. It establishes the exchange-argument justification, the minimize-removals = maximize-kept duality, and the sort-by-end key that the next several problems all reuse.
The next topic, Minimum Number of Arrows to Burst Balloons, is the same earliest-finish greedy in disguise: balloons span horizontal intervals, an arrow shot at an x-coordinate bursts every balloon whose interval contains it, and you want the fewest arrows to burst all. Sorting by end and shooting an arrow at each kept interval's end - bursting every balloon overlapping that point - counts the minimum arrows, exactly mirroring the non-overlapping selection. It reinforces that many distinct-sounding interval problems are the same greedy once you map them onto "group overlapping intervals and act once per group."