839: Sweep Line Algorithm with Event Queue

Difficulty: 4 Level: Advanced Process geometric or temporal events sorted by position — the algorithmic skeleton behind interval union, rectangle area, and line intersection detection.

The Problem This Solves

Many geometric and temporal problems can be solved by imagining a vertical line sweeping from left to right across the plane, processing events (interval starts, ends, intersections) as the line encounters them. Rather than examining all pairs of objects (O(n²)), the sweep line maintains an ordered state of "currently active" objects and updates it as events occur — often reducing complexity to O(n log n). Sweep line algorithms solve: computing the total length/area of a union of intervals/rectangles, reporting all intersecting line segments (Bentley-Ottmann), computing Voronoi diagrams (Fortune's algorithm), and scheduling problems (earliest deadline first, interval colouring). It's the algorithmic paradigm behind many O(n log n) geometry algorithms that would naïvely be O(n²). This example demonstrates sweep line on the interval union problem: given n intervals, compute the total length covered (counting overlaps only once). It also shows the skeleton for more general event processing.

The Intuition

Sort all interval endpoints as events: START events at the left endpoint, END events at the right endpoint. Process events left to right, maintaining a counter of "active intervals." When the counter goes from 0→1 (entering covered territory), start a new covered segment. When it goes from 1→0 (leaving covered territory), close the segment. For the general case, the "state" can be a balanced BST of active segments (ordered by y-coordinate at the current sweep x), with START inserting into the BST, END removing from it, and INTERSECTION events causing adjacent segments to swap order. The event-driven approach is O(n log n): sort events O(n log n), process each event O(log n) with a priority queue and active set.

How It Works in Rust

#[derive(Debug, Clone, PartialEq)]
enum EventType { Start, End }

#[derive(Debug, Clone)]
struct Event {
 x: f64,
 kind: EventType,
 id: usize,
}

fn sweep_line_union(intervals: &[(f64, f64)]) -> f64 {
 if intervals.is_empty() { return 0.0; }

 // Create START and END events for each interval
 let mut events: Vec<Event> = intervals.iter().enumerate()
     .flat_map(|(id, &(lo, hi))| {
         [
             Event { x: lo, kind: EventType::Start, id },
             Event { x: hi, kind: EventType::End,   id },
         ]
     })
     .collect();

 // Sort: by x, with END before START at the same x (avoids counting 0-gap)
 events.sort_by(|a, b| {
     a.x.partial_cmp(&b.x).unwrap()
         .then_with(|| {
             // At same x: process End before Start to avoid double-counting
             match (&a.kind, &b.kind) {
                 (EventType::End, EventType::Start) => std::cmp::Ordering::Less,
                 (EventType::Start, EventType::End) => std::cmp::Ordering::Greater,
                 _ => std::cmp::Ordering::Equal,
             }
         })
 });

 let mut total = 0.0;
 let mut active = 0usize;  // count of active (overlapping) intervals
 let mut cover_start = 0.0; // x where current covered segment started

 for event in &events {
     match event.kind {
         EventType::Start => {
             if active == 0 {
                 cover_start = event.x; // entering covered territory
             }
             active += 1;
         }
         EventType::End => {
             active -= 1;
             if active == 0 {
                 total += event.x - cover_start; // leaving covered territory
             }
         }
     }
 }
 total
}

// Generic event processor skeleton
fn process_events<S, F>(events: &mut Vec<Event>, initial_state: S, handler: F) -> S
where
 F: Fn(S, &Event) -> S,
{
 events.sort_by(|a, b| a.x.partial_cmp(&b.x).unwrap());
 events.iter().fold(initial_state, handler)
}

The tie-breaking rule (END before START at equal x) is critical: two intervals [1, 3] and [3, 5] share endpoint x=3. Without the tie-break, you'd count a gap at 3 that doesn't exist. `then_with` on `Ordering` chains comparisons cleanly — compare by x first, then by event type to break ties. This is the idiomatic Rust multi-key sort pattern. The `process_events` skeleton shows how sweep line generalises: `fold` over sorted events with an evolving state — a functional pattern that maps cleanly from OCaml's `List.fold_left`.

What This Unlocks

Rectangle area union: extend to 2D by running sweep line on x, with a segment tree tracking covered y-length at the current x. O(n log n) for n rectangles.
Bentley-Ottmann line sweep: detect all intersections among n line segments in O((n + k) log n) using a balanced BST of active segments ordered by y.
Scheduling / interval colouring: find the minimum number of machines to run all jobs — equals the maximum overlap depth at any point, which sweep line computes in O(n log n).

Key Differences

Concept	OCaml	Rust
Event type	`type kind = Start \	End`	`enum EventType { Start, End }`
Multi-key sort	`List.sort (fun a b -> ...)` with nested compare	`sort_by` with `.then_with()` chaining
Active counter	Mutable `ref int`	`let mut active = 0usize` — direct
Fold over events	`List.fold_left handler state events`	`events.iter().fold(initial_state, handler)`
Float comparison	`compare` (total order, handles NaN poorly)	`partial_cmp(...).unwrap()` — explicit NaN panic

/// Sweep Line Algorithm with Event Queue.
///
/// Processes interval START/END events in sorted order.
/// Applications: max overlap depth, union length, scheduling.

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum EventKind {
    End = 0,   // Process END before START at same x (avoid double-counting touches)
    Start = 1,
}

#[derive(Debug, Clone, Copy)]
struct Event {
    x: f64,
    kind: EventKind,
}

fn make_events(intervals: &[(f64, f64)]) -> Vec<Event> {
    let mut events: Vec<Event> = intervals
        .iter()
        .flat_map(|&(lo, hi)| [
            Event { x: lo, kind: EventKind::Start },
            Event { x: hi, kind: EventKind::End },
        ])
        .collect();
    // Sort by x; at same x, END before START
    events.sort_by(|a, b| {
        a.x.partial_cmp(&b.x).unwrap()
            .then(a.kind.cmp(&b.kind))
    });
    events
}

/// Maximum number of intervals active simultaneously.
pub fn max_overlap(intervals: &[(f64, f64)]) -> usize {
    let events = make_events(intervals);
    let mut active = 0i64;
    let mut best = 0usize;
    for ev in &events {
        match ev.kind {
            EventKind::Start => {
                active += 1;
                best = best.max(active as usize);
            }
            EventKind::End => active -= 1,
        }
    }
    best
}

/// Total length covered by the union of intervals.
pub fn union_length(intervals: &[(f64, f64)]) -> f64 {
    let events = make_events(intervals);
    let mut active = 0i64;
    let mut total = 0.0f64;
    let mut prev_x = 0.0f64;

    for ev in &events {
        if active > 0 {
            total += ev.x - prev_x;
        }
        prev_x = ev.x;
        match ev.kind {
            EventKind::Start => active += 1,
            EventKind::End => active -= 1,
        }
    }
    total
}

/// Find all intervals that contain point x (sweep-line approach).
pub fn intervals_at(x: f64, intervals: &[(f64, f64)]) -> Vec<usize> {
    intervals.iter()
        .enumerate()
        .filter(|(_, &(lo, hi))| lo <= x && x <= hi)
        .map(|(i, _)| i)
        .collect()
}

fn main() {
    let ivs: &[(f64, f64)] = &[(1.0, 4.0), (2.0, 6.0), (3.0, 5.0), (7.0, 9.0)];
    println!("Intervals: [1,4] [2,6] [3,5] [7,9]");
    println!("Max overlap:  {} (expected 3, at [3,4])", max_overlap(ivs));
    println!("Union length: {:.1} (expected 7.0: [1,6]∪[7,9])", union_length(ivs));

    let touching: &[(f64, f64)] = &[(0.0, 1.0), (1.0, 2.0), (2.0, 3.0)];
    println!("\nTouching intervals [0,1] [1,2] [2,3]:");
    println!("Max overlap:  {} (expected 1)", max_overlap(touching));
    println!("Union length: {:.1} (expected 3.0)", union_length(touching));

    // Meeting-room scheduling: how many rooms do we need?
    let meetings: &[(f64, f64)] = &[(0.0, 30.0), (5.0, 10.0), (15.0, 20.0)];
    println!("\nMeetings [0,30] [5,10] [15,20]: need {} rooms", max_overlap(meetings));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_max_overlap() {
        assert_eq!(max_overlap(&[(1.0, 4.0), (2.0, 6.0), (3.0, 5.0)]), 3);
    }

    #[test]
    fn test_no_overlap() {
        assert_eq!(max_overlap(&[(1.0, 2.0), (3.0, 4.0), (5.0, 6.0)]), 1);
    }

    #[test]
    fn test_touching_not_overlapping() {
        // Touching intervals [0,1] [1,2] [2,3] — at each point only 1 active
        assert_eq!(max_overlap(&[(0.0, 1.0), (1.0, 2.0), (2.0, 3.0)]), 1);
    }

    #[test]
    fn test_union_length_basic() {
        let ivs: &[(f64, f64)] = &[(1.0, 4.0), (2.0, 6.0), (3.0, 5.0), (7.0, 9.0)];
        let u = union_length(ivs);
        assert!((u - 7.0).abs() < 1e-9, "union={u}");
    }

    #[test]
    fn test_union_length_disjoint() {
        let ivs: &[(f64, f64)] = &[(0.0, 1.0), (2.0, 3.0), (4.0, 5.0)];
        assert!((union_length(ivs) - 3.0).abs() < 1e-9);
    }

    #[test]
    fn test_union_length_nested() {
        // [0,10] contains [2,5] — union is 10
        assert!((union_length(&[(0.0, 10.0), (2.0, 5.0)]) - 10.0).abs() < 1e-9);
    }

    #[test]
    fn test_touching_union() {
        // [0,1] [1,2] [2,3] — union is 3
        assert!((union_length(&[(0.0, 1.0), (1.0, 2.0), (2.0, 3.0)]) - 3.0).abs() < 1e-9);
    }

    #[test]
    fn test_meeting_rooms() {
        // [0,30] [5,10] [15,20]: max 2 overlapping at any point
        assert_eq!(max_overlap(&[(0.0, 30.0), (5.0, 10.0), (15.0, 20.0)]), 2);
    }
}

(* Sweep Line Algorithm in OCaml *)

type interval = { lo: float; hi: float }

(* Event type: 0 = END (process before START at same x), 1 = START *)
type event = { x: float; kind: int; (* 0=end, 1=start *) }

let make_events (intervals : interval list) : event list =
  List.concat_map (fun iv ->
    [{ x = iv.lo; kind = 1 }; { x = iv.hi; kind = 0 }]
  ) intervals
  |> List.sort (fun a b ->
    let cx = compare a.x b.x in
    if cx <> 0 then cx else compare a.kind b.kind)  (* END before START *)

(* Maximum overlap depth: max # of intervals active at any point *)
let max_overlap (intervals : interval list) : int =
  let events = make_events intervals in
  let active = ref 0 and best = ref 0 in
  List.iter (fun ev ->
    if ev.kind = 1 then begin incr active; if !active > !best then best := !active end
    else decr active
  ) events;
  !best

(* Total length of union of intervals *)
let union_length (intervals : interval list) : float =
  let events = make_events intervals in
  let active = ref 0 and total = ref 0.0 and prev_x = ref 0.0 in
  List.iter (fun ev ->
    if !active > 0 then total := !total +. (ev.x -. !prev_x);
    prev_x := ev.x;
    if ev.kind = 1 then incr active else decr active
  ) events;
  !total

(* All points with maximum overlap — just return max value here *)
let () =
  let ivs = [
    {lo=1.0; hi=4.0};
    {lo=2.0; hi=6.0};
    {lo=3.0; hi=5.0};
    {lo=7.0; hi=9.0};
  ] in
  Printf.printf "Intervals: [1,4] [2,6] [3,5] [7,9]\n";
  Printf.printf "Max overlap depth: %d  (expected 3 at [3,4])\n" (max_overlap ivs);
  Printf.printf "Union length: %.1f  (expected 7.0: [1,6]∪[7,9])\n" (union_length ivs);

  (* Touching intervals — should not count as overlapping *)
  let touching = [{lo=0.0;hi=1.0}; {lo=1.0;hi=2.0}; {lo=2.0;hi=3.0}] in
  Printf.printf "\nTouching intervals [0,1] [1,2] [2,3]:\n";
  Printf.printf "Max overlap: %d  (expected 1)\n" (max_overlap touching);
  Printf.printf "Union length: %.1f  (expected 3.0)\n" (union_length touching)