Intervals and greedy choices

Sorting often makes a problem easier to reason about. Sorting intervals by start puts possible overlaps next to each other. Sorting jobs by end time can reveal a safe choice. Sorting coordinates turns "closest" questions into questions about neighbors.

To merge intervals, go through them in order of start, and keep the merged result so far. Only the last merged interval can be extended by the next one. Whether touching intervals overlap depends on the problem. Closed intervals like [1, 2] and [2, 3] merge. But for bookings from start up to (not including) end, a booking ending at time 2 frees the room before one starting at time 2.

To fit the most intervals with no overlaps, always pick the one that ends earliest. Why is that safe? Take a best schedule that starts with a different interval, which ends later. Swap in the earliest-ending one. It leaves at least as much room for everything after it, so the schedule is just as big. Repeat for the rest. Showing a swap never hurts like this is called an exchange argument.

pub fn max_nonoverlap(intervals: &mut [(i32, i32)]) -> usize {
    assert!(intervals.iter().all(|&(s, e)| s < e));
    intervals.sort_unstable_by_key(|&(s, e)| (e, s));
    let (mut last_end, mut count) = (None, 0);
    for &(start, end) in intervals.iter() {
        if last_end.is_none_or(|prev| start >= prev) {
            count += 1;
            last_end = Some(end);
        }
    }
    count
}

This treats intervals as running from start up to (not including) end, and maximizes the count. If intervals have different values, swapping in an earlier-ending one can lose value. Weighted scheduling needs DP instead: sort, then for each interval find the last one that fits before it.

To count meeting rooms, sweep through starts and ends while counting how many meetings are running, or keep a min-heap of end times. Decide what happens when a start and an end tie. A heap tells you which room frees up first; it doesn't prove a greedy choice is right on its own.

Practice: LC 56 Merge Intervals, LC 57 Insert Interval, LC 435 Non-overlapping Intervals, LC 452 Minimum Number of Arrows to Burst Balloons, LC 55 Jump Game, LC 45 Jump Game II, LC 1235 Maximum Profit in Job Scheduling.

Check your understanding: Can you swap your choice into a best solution without making it worse? What makes that swap safe? Build the smallest example where the swap fails once the goal changes.