Table of contents
Open Table of contents
Problem
Given an array of intervals intervals
where intervals[i] = [starti, endi]
, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
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.
Example 2:
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.
Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Constraints:
1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4
Approaches
This problem aims to minimize the number of interval removals to prevent overlaps. We can achieve this efficiently using a greedy algorithm.
Greedy Algorithm:
- Sort Intervals: Sort the intervals based on their end times.
- Iterate and Compare: Iterate through the sorted intervals. If the current interval starts before the end of the previous interval, it’s overlapping, and we increment our removal count.
- Keep Track of Non-Overlapping End: Update the end time of the last non-overlapping interval for comparison in future iterations.
Solution: Greedy Algorithm
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
# Sort intervals based on their end time
intervals.sort(key=lambda x: x[1])
# Initialize the end time of the first interval
end = intervals[0][1]
count = 0
# Iterate through the intervals
for i in range(1, len(intervals)):
if intervals[i][0] < end:
# Increment count if overlapping
count += 1
else:
# Update end time for next comparison
end = intervals[i][1]
return count
Time and Memory Complexity
The time complexity of this solution is O(n log n), primarily due to the sorting step, where n is the number of intervals. The space complexity is O(1), as we are only using a few extra variables for tracking.
Explanation
The key to this solution is sorting the intervals by their end time. This allows us to efficiently check for overlaps. If an interval starts before the end of the last non-overlapping interval, it’s overlapping, and we need to remove it. We keep updating the end time of the last non-overlapping interval for subsequent comparisons.
Visual Representation
Consider the input intervals = [[1,2],[2,3],[3,4],[1,3]]
.
-
Sorting:
- Sorted Intervals:
[[1,2], [1,3], [2,3], [3,4]]
.
- Sorted Intervals:
-
Iteration and Comparison:
- Start with
[1,2]
, end time is 2. - Next is
[1,3]
, starts before end of[1,2]
(overlap), remove[1,3]
, increment count. - Then
[2,3]
, no overlap with[1,2]
, update end to 3. - Finally
[3,4]
, no overlap with[2,3]
.
- Start with
-
Result:
- One interval (
[1,3]
) was removed.
- One interval (
Intervals: [[1,2],[1,3],[2,3],[3,4]]
|
V
Sorted: [[1,2], [1,3], [2,3], [3,4]]
|
V
Remove [1,3] (overlap with [1,2])
|
V
Remaining: [[1,
2], [2,3], [3,4]]
|
V
Minimum Removals: 1
By applying this greedy strategy, we ensure the minimum number of intervals are removed to achieve non-overlapping intervals.