Remove Overlaps
To find the maximum number of non-overlapping intervals: sort by END time, then greedily pick the earliest-ending interval that doesn't conflict with the last picked one.
How It Works
To keep the maximum number of non-overlapping intervals (equivalently, remove the minimum number to eliminate overlaps), sort by end time and greedily take every interval that starts at or after the last accepted interval's end. Finishing earliest leaves the most room for everything that follows, which is the exchange argument proving the greedy optimal.
A dynamic-programming formulation over sorted intervals also works but runs in O(n²) or needs binary search to reach O(n log n); the greedy achieves O(n log n) from the sort plus a trivial O(n) sweep with O(1) extra state — just the end of the last kept interval. This is the classic activity-selection problem in interval-scheduling clothing.
Step-by-Step Visualization
Code
static int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int end = Integer.MIN_VALUE, removals = 0;
for (int[] iv : intervals) {
if (iv[0] >= end) end = iv[1];
else removals++;
}
return removals;
}
// eraseOverlapIntervals({{1,2},{2,3},{3,4},{1,3}}) → 1Tips & Gotchas
Practice Problems
- 1Non-overlapping Intervals
- 2Minimum Number of Arrows to Burst Balloons
- 3Maximum Length of Pair Chain
About the Intervals Pattern
Problems involving ranges [start, end] — meetings, schedules, overlapping segments. The key first step is almost always: sort by start time (or end time). Then process them linearly.
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Common Array Interview Problems
- Two Sum
- Best Time to Buy & Sell Stock
- Maximum Subarray
- Merge Intervals
- Product of Array Except Self
- Container With Most Water
Frequently Asked Questions
Why does sorting by end time work here when merging sorts by start?
The goals differ: merging must group everything that touches, so it processes ranges in the order they begin, while selection wants to finish each commitment as early as possible to leave room for future ones. Choosing the earliest-ending compatible interval can always be exchanged into any optimal solution without loss.
How does Burst Balloons with arrows map onto this technique?
Each arrow's position is a point that must stab a group of mutually overlapping balloons, so the answer equals the number of non-overlapping groups. Sort by end, shoot at the first balloon's end, and skip every balloon that overlap-contains that point — a direct reskin of the greedy.