Non-overlapping Intervals
Given an array of 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.
Problem
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Interactive Visualization
fun eraseOverlapIntervals(intervals: Array<IntArray>): Int { intervals.sortBy { it[1] } var count = 0 var end = Int.MIN_VALUE for (interval in intervals) { if (interval[0] >= end) { end = interval[1] } else { count++ } } return count }
Explanation
Key Insight
The greedy approach works by always keeping the interval that ends earliest. This leaves the maximum room for future intervals. Sort intervals by end time, then iterate through them. If an interval doesn't overlap with the previous kept interval, keep it. Otherwise, remove it.
Algorithm
- Sort: Sort all intervals by their end time in ascending order
- Initialize: Set count = 0 (removed intervals) and end = -∞ (last kept interval's end)
- Iterate: For each interval:
- If interval.start >= end: The interval doesn't overlap, keep it and update end
- Otherwise: The interval overlaps, remove it and increment count
- Return: Return count (minimum intervals to remove)
Complexity Analysis
- Time Complexity: O(n log n) - Sorting takes O(n log n), iteration takes O(n)
- Space Complexity: O(1) - Only using constant extra space (assuming in-place sort)