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;