Non-overlapping Intervals — Interval Scheduling
Sanjeev SharmaAdvertisement
Problem
Remove minimum number of intervals so the rest don't overlap.
Approach — Greedy by End Time
Sort by end. Greedily keep intervals that don't overlap with the last kept. Count removals.
Time: O(n log n) | Space: O(1)
Solutions
Python
class Solution:
def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x:x[1])
removed=0; prev_end=float('-inf')
for start,end in intervals:
if start>=prev_end: prev_end=end
else: removed+=1
return removed
C++
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& iv){
sort(iv.begin(),iv.end(),[](auto& a,auto& b){return a[1]<b[1];});
int rm=0; long pe=LLONG_MIN;
for(auto& i:iv){if(i[0]>=pe)pe=i[1];else rm++;}
return rm;
}
};
Complexity
- Time: O(n log n) | Space: O(1)
Advertisement
