Pattern Reference
Greedy Intervals
"Interval scheduling, interval partitioning, meeting rooms, merge intervals, insert interval."
Loading...
Deep Dive Tutorial
Activity selection greedy: sort by end time. Always pick the interval with the earliest end time that doesn't conflict with the last picked. This is optimal. Meeting rooms: sweep events (start: +1, end: -1), track running max of concurrent events. Interval covering: sort by start, greedily extend reach. Jump Game variant: how far can you reach from current position?
Activity selection and meeting rooms templates
// Maximum non-overlapping intervals (activity selection)
function maxNonOverlapping(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // sort by end time
let count = 0, lastEnd = -Infinity;
for (const [start, end] of intervals) {
if (start >= lastEnd) { // no overlap with last selected
count++;
lastEnd = end;
}
}
return count;
}
// Minimum meeting rooms needed
function minMeetingRooms(intervals) {
const events = [];
for (const [s, e] of intervals) {
events.push([s, 1]); // start
events.push([e, -1]); // end (end first if tie, so use -1 in sort)
}
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // end before start at same time
let rooms = 0, maxRooms = 0;
for (const [, type] of events) {
rooms += type;
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Worked Problems
calendar
Interval sorting strategies:
- By end time: maximize non-overlapping (activity selection)
- By start time: covering problems (Jump Game, Video Stitching)
- Both sorted: two-pointer meeting rooms trick
Proof of optimality for activity selection: Exchange argument — if any optimal solution doesn't pick the earliest-ending interval, we can swap it in without reducing the count.
Common trap: Intervals that touch (end == start) — define as overlapping or not? Always clarify. For meeting rooms: [1,2] and [2,3] — if end is exclusive, no overlap; if inclusive, they share time 2.
- By end time: maximize non-overlapping (activity selection)
- By start time: covering problems (Jump Game, Video Stitching)
- Both sorted: two-pointer meeting rooms trick
Proof of optimality for activity selection: Exchange argument — if any optimal solution doesn't pick the earliest-ending interval, we can swap it in without reducing the count.
Common trap: Intervals that touch (end == start) — define as overlapping or not? Always clarify. For meeting rooms: [1,2] and [2,3] — if end is exclusive, no overlap; if inclusive, they share time 2.