Non-Overlapping Intervals
- mosesg1123
- 2 days ago
- 4 min read
Managing schedules and resources is everywhere in the real world. Whether it’s video playback buffers, CPU job scheduling, or booking conference rooms, overlapping intervals cause conflicts. This problem is a great warm-up for greedy thinking and practicing pattern recognition around intervals.
Problem Statement
You are given an array of intervals where each interval is represented as [start, end]. Your goal is to remove the minimum number of intervals so that the rest do not overlap. Return that minimum number.
Example:
Input: [[1,3], [2,4], [3,5]]
Output: 1
Reason: Removing [2,4] leaves two non-overlapping intervals.
1. Clarify Requirements Before Jumping Into Code
I want to be sure what counts as overlap. If one interval ends exactly where another starts, that does not count as overlap.
Intervals can be in any order
Output is just the count of removed intervals, not the resulting list.
2. Identify the Category of the Question
Our first instinct for a solution here is to walk through the intervals in order and just kick out the intervals that overlap. We're trusting that we will find the optimal global solution by zooming into a small subset of intervals and making a local decision. That is the essence of a greedy algorithm, making that the likely category for this question.
Additionally, since intervals can be provided in any order, I may need to consider sorting the input. That's also a decent hint that greedy algorithm may be the solution here, since many greedy algorithms require sorting as a pre-processing step.
3. Consider a Brute-Force Approach to Understand the Problem
Imagine we wanted to be 100% confident that we had the best possible solution to this problem. To do that, we would probably need to try every possible subset of non-overlapping intervals. Then we can simply pick the largest, and subtract that from the total number of intervals to get our result.
But that's a lot of processing. We're generating O(2^n) subsets - definitely too slow for our runtime.
It's important to remember that greedy algorithms don't guarantee the best possible solution, but sometimes that's ok, especially when the alternative is so much worse.
4. Brainstorm More Solutions
The fact that the input doesn't have any input complicates the problem, since the only way to identify the next best possible interval in my solution is to scan the whole set.
So, what if we start by sorting the input? That way, we know exactly where we need to look for the next interval.
The question then becomes, how do we sort? We have two options: we can sort by the start time of an interval or we can sort by the end time. Let's check both.
Option 1: Sort by Start Time, Then Check Overlaps
So we sort all of the intervals by start time in O(n log n) time. We start iterating through our sorted input and find a couple of intervals that overlap. Which one do we keep?
We already sorted on the start time, so let's think about what we can do with the other half of the interval - the end time. Do we keep the interval that ends sooner or the interval that ends later?
Keeping the one the interval that ends later could potentially block future intervals. So let's choose the greedy option - keep the interval that ends soonest so that we can maximize the amount of time we have open for future potential intervals.
Iterating through our input costs O(n) time, giving us a total runtime complexity of O(n log n).
Option 2: Sort by End + Greedy Selection
Now let's think about how our solution would change if we sorted by the end time.
At the end of the day, we're still doing the same thing as in Option 1 - choosing the greedy option by keeping the intervals that end soonest. The difference is that Option 2 makes it much easier to identify which intervals end soonest, leading to some cleaner code.
So, of the two options here, sorting by end time is preferred!
Complexity
Sorting: O(n log n)
Scanning: O(n)
Final runtime: O(n log n)
Final chosen solution → Greedy by earliest end time ✅
5. Discuss Trade-Offs Between Your Solutions
6. Write Pseudocode to Structure Your Thoughts
function eraseOverlapIntervals(intervals):
sort intervals by end ascending
countKeep = 1
prevEnd = intervals[0].end
for i from 1 to intervals.length - 1:
if intervals[i].start >= prevEnd:
countKeep += 1
prevEnd = intervals[i].end
return intervals.length - countKeep
7. Consider Edge Cases
Empty list → 0 removals
Only one interval → 0 removals
Intervals fully overlapping → remove all but one
Already sorted or already non-overlapping — minimal removals
8. Write Full Code Syntax (Java)
import java.util.Arrays;
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int countKeep = 1;
int prevEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= prevEnd) {
countKeep++;
prevEnd = intervals[i][1];
}
}
return intervals.length - countKeep;
}
}
9. Test Your Code
System.out.println(new Solution().eraseOverlapIntervals(
new int[][]{{1,2},{2,3},{3,4},{1,3}})); // 1
System.out.println(new Solution().eraseOverlapIntervals(
new int[][]{{1,2},{1,2},{1,2}})); // 2
System.out.println(new Solution().eraseOverlapIntervals(
new int[][]{{1,2},{2,3}})); // 0
System.out.println(new Solution().eraseOverlapIntervals(
new int[][]{})); // 0
System.out.println(new Solution().eraseOverlapIntervals(
new int[][]{{0,10},{1,5},{6,9}})); // 1
10. Key Lessons to Remember for Future Questions
Greedy algorithms often involve some kind of pre-processing with sorting
Intervals that end earlier leave more space for others
This same strategy applies to scheduling CPU jobs, networking windows, and event timelines
Comments