Greedy Algorithms

A greedy algorithm builds a solution step by step, making the locally optimal choice at each decision point without backtracking. When a problem exhibits the greedy-choice property and optimal substructure, sorting the input (sort_unstable_by_key) or maintaining a priority queue (BinaryHeap) yields the globally optimal answer in $O(n \log n)$ time.

Classic Greedy Sorting Strategies:
  1. Interval Scheduling (Max Non-Overlapping Events):
     ---> Sort intervals by END time ascending (`|iv| iv.end`)!
  2. Interval Merging / Sweep-Line (Overlapping Windows):
     ---> Sort intervals by START time ascending (`|iv| iv.start`)!
  3. Deadline / Regret Minimization (Course Schedule / Job Sequencing):
     ---> Sort by deadline ascending + evict longest-duration taken job via Max-Heap!

1. Maximum Non-Overlapping Intervals (Earliest End Time First)

To select the maximum number of mutually compatible intervals [start, end) from a set of $N$ intervals:

• Sort by end time ascending (intervals.sort_unstable_by_key(|iv| iv.1)).
• Greedily pick every interval whose start >= last_end:

/// Selects the maximum number of non-overlapping half-open intervals `[start, end)`
/// in O(n log n) time by sorting by earliest end time.
pub fn max_disjoint_intervals(mut intervals: Vec<(i64, i64)>) -> Vec<(i64, i64)> {
    intervals.sort_unstable_by_key(|&(_start, end)| end);

    let mut chosen = Vec::new();
    let mut last_end = i64::MIN;

    for (start, end) in intervals {
        if start >= last_end {
            chosen.push((start, end));
            last_end = end;
        }
    }

    chosen
}

2. Merging Overlapping Intervals & Sweep-Line Peak Concurrency

Sorting intervals by start time enables merging overlapping intervals in a single pass, while sorting (timestamp, +1 / -1) event points (Sweep-Line algorithm) computes the maximum number of simultaneously active intervals (such as minimum conference rooms or peak concurrent network connections):

/// Merges all overlapping or touching intervals `[start, end]` in O(n log n) time.
pub fn merge_intervals(mut intervals: Vec<(i64, i64)>) -> Vec<(i64, i64)> {
    if intervals.is_empty() {
        return Vec::new();
    }
    intervals.sort_unstable();

    let mut merged = Vec::with_capacity(intervals.len());
    let mut current = intervals[0];

    for &(start, end) in &intervals[1..] {
        if start <= current.1 {
            // Overlaps with `current`; extend the right endpoint:
            current.1 = current.1.max(end);
        } else {
            merged.push(current);
            current = (start, end);
        }
    }
    merged.push(current);
    merged
}

/// Computes the peak number of simultaneously active half-open intervals `[start, end)`
/// using an O(n log n) event sweep-line.
pub fn peak_concurrent_intervals(intervals: &[(i64, i64)]) -> usize {
    let mut events = Vec::with_capacity(intervals.len() * 2);
    for &(start, end) in intervals {
        // Place `-1` (end event) BEFORE `+1` (start event) at the exact same timestamp `t`
        // so half-open intervals `[10, 20)` and `[20, 30)` do not count as overlapping at 20!
        events.push((start, 1isize));
        events.push((end, -1isize));
    }
    events.sort_unstable();

    let mut active = 0isize;
    let mut peak = 0isize;
    for (_, delta) in events {
        active += delta;
        peak = peak.max(active);
    }
    peak as usize
}

fn main() {
    let raw = vec![(1, 4), (2, 3), (3, 6), (7, 9)];
    let disjoint = max_disjoint_intervals(raw.clone());
    assert_eq!(disjoint, vec![(2, 3), (3, 6), (7, 9)]);

    let merged = merge_intervals(raw.clone());
    assert_eq!(merged, vec![(1, 6), (7, 9)]);

    let peak = peak_concurrent_intervals(&raw);
    assert_eq!(peak, 2);

    println!("Max disjoint: {disjoint:?}, Merged: {merged:?}, Peak concurrent: {peak}");
}

Max disjoint: [(2, 3), (3, 6), (7, 9)], Merged: [(1, 6), (7, 9)], Peak concurrent: 2