🟨 Non-overlapping Intervals (#435)
🔗 Problem Link
📋 Problem Statement
Given an array of 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.
💡 Examples
Example 1
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed.
Example 2
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
🔑 Key Insights & Approach
Core Observation: Greedy - sort by end time, always keep interval with earliest end.
Why Greedy?
- O(n log n) time for sort
- Sort by end time
- Remove intervals that overlap with earliest ending
Pattern: "Interval Scheduling" greedy pattern.
🐍 Solution: Python
Approach: Greedy - Sort by End Time
Time Complexity: O(n log n) | Space Complexity: O(1)
from typing import List
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
count = 0
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] < end:
count += 1
else:
end = intervals[i][1]
return count
🔵 Solution: Golang
Approach: Greedy
Time Complexity: O(n log n) | Space Complexity: O(1)
import "sort"
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
count := 0
end := intervals[0][1]
for i := 1; i < len(intervals); i++ {
if intervals[i][0] < end {
count++
} else {
end = intervals[i][1]
}
}
return count
}