Coverage / removal (Intervals Sub-pattern)
Choose which intervals to keep or use. To fit in as many as possible, sort by end and keep the earliest finisher. To cover a whole range with as few as possible, sort by start and keep extending the farthest reach.
- ›
"minimum number of intervals to remove so the rest don't overlap"
- ›
"minimum number of arrows to burst all balloons"
- ›
"fewest clips to cover [0, time]"
- ›
"fewest taps to water the whole garden"
Non-overlapping Intervals and Burst Balloons are the same earliest-end greedy; the only difference is touching ends (they don't overlap in LC 435, but one arrow bursts both in LC 452). Video Stitching and Taps cover a range: from the current covered end, pick the interval that reaches farthest, like Jump Game II. Taps first turn (i, range) into [i − range, i + range], clamped to [0, n].
Questions
ordered from “learn the idea” to “recognise it without help”- 1Non-overlapping IntervalsWalkthroughMediumBasic Anchor·LeetCode #435
- 2Minimum Number of Arrows to Burst BalloonsWalkthroughMediumBasic Reinforcement·LeetCode #452
- 3Video StitchingWalkthroughMediumMedium·LeetCode #1024
- 4Minimum Number of Taps to Open to Water a GardenWalkthroughHardTricky / Edge Case·LeetCode #1326
Template
// Non-overlapping Intervals: fewest removals = n - most intervals we can keep.
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; }); // by END
int kept = 0;
long long lastEnd = LLONG_MIN;
for (auto& in : intervals) {
if (in[0] >= lastEnd) { // fits after the last kept one
kept++;
lastEnd = in[1]; // earliest finisher leaves most room
}
}
return (int)intervals.size() - kept;
}