Q28: Non-overlapping Intervals
Given an array of intervals intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Greedy End-Time Interval Removal
function eraseOverlapIntervals(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[1] - b[1]); // Sort by end time
let count = 0;
let prevEnd = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < prevEnd) {
count++; // Overlap detected; remove current interval
} else {
prevEnd = intervals[i][1]; // No overlap; update prevEnd
}
}
return count;
}
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1💡 Sorting by end times allows greedily keeping intervals that finish earliest. If the next interval starts before
prevEnd, it must be removed to prevent overlap.Key Takeaways
- Greedy strategy: sort intervals by end time to preserve maximum remaining space.
- Always pick the interval with the earliest end time to minimize collisions with future intervals.
Knowledge Check
Why do we sort by end time rather than start time for greedy interval scheduling?