Non-overlapping Intervals
Problem link: https://leetcode.com/problems/non-overlapping-intervals/
Problem Statement
Given an array of intervals intervals where intervals[i] = [start, end], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Input
- intervals: [[start, end]]
Output
- Return minimum number of intervals to remove
Example
intervals = [[1,2],[2,3],[3,4],[1,3]]
Explanation
We remove [1,3] to make the rest non-overlapping.
Remaining: [[1,2],[2,3],[3,4]]
Answer = 1
Brute Force
Intuition
Try removing each interval and check if the remaining intervals are non-overlapping. Track minimum removals.
Approach
- Generate subsets by removing intervals
- Check if remaining intervals are non-overlapping
- Track minimum removals
Dry Run
Input: [[1,2],[2,3],[3,4],[1,3]]
Remove [1,3] → valid → removals = 1 Try others → invalid
Minimum = 1
Visualization
Code (Java)
// Brute force is exponential and not practical
Complexity Analysis
All subsets explored → exponential complexity.
Optimal Solution
Intuition
To minimize removals, maximize number of non-overlapping intervals. Use greedy: always pick interval with smallest end time.
Approach
- Sort by end time
- Traverse intervals
- If overlap → remove
- Else → update prevEnd
Dry Run
Sort → [[1,2],[1,3],[2,3],[3,4]]
Pick [1,2] [1,3] overlaps → remove [2,3] keep [3,4] keep
Answer = 1
Visualization
Code (Java)
import java.util.*;
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0;
int prevEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < prevEnd) {
count++;
} else {
prevEnd = intervals[i][1];
}
}
return count;
}
}
Complexity Analysis
Sorting dominates → O(N log N).
Quick Revision (Brute Force)
- Try all removals
- Check validity
- Exponential
Quick Revision (Optimal)
- Sort by end
- Greedy pick
- Remove overlaps