Skip to main content

logicaffeine_proof/
interval_sched.rs

1//! Interval scheduling in O(n log n) via a sweep line — the matching/Hall reasoner reaching into
2//! resource allocation over time.
3//!
4//! Given `n` tasks, each an interval `[start, end)`, and `m` interchangeable machines (or green
5//! windows, or registers), can every task run with no two overlapping tasks on one machine? This is
6//! colouring the tasks' **interval graph** (overlap = edge), and interval graphs are *perfect*, so
7//! the chromatic number equals the largest clique — here, the maximum number of tasks overlapping at
8//! any instant. Hence it is feasible **iff peak overlap ≤ m**, decided by one sweep over the
9//! endpoints. When it overflows, the `m+1` tasks active at the peak are a clique that needs `m+1`
10//! machines — a Hall/pigeonhole certificate, exactly the structure Z3 grinds in the colouring
11//! encoding but we settle in near-linear time. Both outcomes are independently re-checkable.
12
13/// A half-open task interval `[start, end)`.
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub struct Interval {
16    /// Inclusive start.
17    pub start: i64,
18    /// Exclusive end.
19    pub end: i64,
20}
21
22impl Interval {
23    /// Construct `[start, end)`.
24    pub fn new(start: i64, end: i64) -> Self {
25        Interval { start, end }
26    }
27}
28
29/// The outcome of scheduling onto `m` machines.
30#[derive(Clone, Debug, PartialEq, Eq)]
31pub enum ScheduleOutcome {
32    /// Every task placed: `assignment[i]` is task `i`'s machine in `0..m` (re-checkable via
33    /// [`is_valid_schedule`]).
34    Feasible(Vec<usize>),
35    /// No schedule exists, witnessed by a set of mutually-overlapping tasks larger than `m`
36    /// (re-checkable via [`is_overflow_witness`]).
37    Infeasible(Vec<usize>),
38}
39
40/// Two half-open intervals overlap iff each starts before the other ends.
41#[inline]
42fn overlaps(a: &Interval, b: &Interval) -> bool {
43    a.start < b.end && b.start < a.end
44}
45
46/// Decide whether `tasks` can be scheduled on `machines` machines. Sweeps the endpoints to find the
47/// peak overlap: feasible iff that peak is ≤ `machines`, with a greedy interval colouring as the
48/// assignment, else the overflowing overlap-clique as the certificate.
49pub fn schedule_or_overflow(tasks: &[Interval], machines: usize) -> ScheduleOutcome {
50    // Endpoint events; at equal times an end (-1) precedes a start (+1) so touching intervals
51    // [a,b) and [b,c) are never counted as simultaneously active.
52    let mut events: Vec<(i64, i8, usize)> = Vec::with_capacity(tasks.len() * 2);
53    for (i, t) in tasks.iter().enumerate() {
54        if t.start < t.end {
55            events.push((t.start, 1, i));
56            events.push((t.end, -1, i));
57        }
58    }
59    events.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(&b.1)));
60    let mut active: Vec<usize> = Vec::new();
61    for (_, delta, idx) in &events {
62        if *delta == 1 {
63            active.push(*idx);
64            if active.len() > machines {
65                // Every active task overlaps every other (all contain this instant) — a clique.
66                return ScheduleOutcome::Infeasible(active.clone());
67            }
68        } else {
69            active.retain(|&x| x != *idx);
70        }
71    }
72    ScheduleOutcome::Feasible(greedy_assign(tasks, machines))
73}
74
75/// The peak number of tasks active simultaneously — the interval graph's clique number / chromatic
76/// number, i.e. the fewest machines (or registers) that suffice. One sweep, O(n log n).
77pub fn peak_concurrency(tasks: &[Interval]) -> usize {
78    let mut events: Vec<(i64, i8)> = Vec::with_capacity(tasks.len() * 2);
79    for t in tasks {
80        if t.start < t.end {
81            events.push((t.start, 1));
82            events.push((t.end, -1));
83        }
84    }
85    events.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(&b.1)));
86    let (mut cur, mut peak) = (0i64, 0i64);
87    for (_, d) in events {
88        cur += d as i64;
89        peak = peak.max(cur);
90    }
91    peak as usize
92}
93
94/// Greedy interval colouring: tasks in start order each take the lowest machine free by their start.
95/// Uses at most the peak-overlap many machines, so when peak ≤ `machines` it always succeeds.
96fn greedy_assign(tasks: &[Interval], machines: usize) -> Vec<usize> {
97    let mut order: Vec<usize> = (0..tasks.len()).collect();
98    order.sort_by_key(|&i| tasks[i].start);
99    let mut free_at = vec![i64::MIN; machines.max(1)];
100    let mut assignment = vec![0usize; tasks.len()];
101    for &i in &order {
102        let m = (0..free_at.len())
103            .find(|&m| free_at[m] <= tasks[i].start)
104            .unwrap_or(0);
105        free_at[m] = tasks[i].end;
106        assignment[i] = m;
107    }
108    assignment
109}
110
111/// Re-check a schedule: every assigned machine is in range and no two overlapping tasks share one.
112pub fn is_valid_schedule(tasks: &[Interval], machines: usize, assignment: &[usize]) -> bool {
113    if assignment.len() != tasks.len() || assignment.iter().any(|&m| m >= machines) {
114        return false;
115    }
116    for i in 0..tasks.len() {
117        for j in (i + 1)..tasks.len() {
118            if assignment[i] == assignment[j] && overlaps(&tasks[i], &tasks[j]) {
119                return false;
120            }
121        }
122    }
123    true
124}
125
126/// Re-check an overflow witness: all the listed tasks pairwise overlap and there are more than
127/// `machines` of them — a clique that cannot be coloured with `machines` colours.
128pub fn is_overflow_witness(tasks: &[Interval], machines: usize, witness: &[usize]) -> bool {
129    if witness.len() <= machines {
130        return false;
131    }
132    witness.iter().enumerate().all(|(a, &i)| {
133        i < tasks.len()
134            && witness
135                .iter()
136                .skip(a + 1)
137                .all(|&j| j < tasks.len() && overlaps(&tasks[i], &tasks[j]))
138    })
139}
140
141#[cfg(test)]
142#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/interval_sched/tests.rs"]
143mod tests;