Minimize Late Jobs (Rust)
Topics: scheduling, greedy, binary heap, Moore–Hodgson
Problem
You have jobs to run on one machine, each with a length and a deadline (all available at
time 0, run one at a time). You can't finish them all on time, so maximize how many do.
#[derive(Clone, Copy)]
pub struct Job { pub length: i64, pub deadline: i64 }
pub fn max_on_time(jobs: &[Job]) -> usize;
- Return the maximum count of jobs that complete by their deadline.
- You choose both the subset and the order; unpicked jobs are dropped.
- The answer must not depend on input order.
(1,2) (2,3) (3,4) → 2 (total length 6 > last deadline 4)
(4,4) (2,5) (2,6) → 2 (drop the length-4 job, keep both length-2 jobs)
(1,5) (1,5) (1,5) → 3
This is Moore–Hodgson: walk the jobs in deadline order, tentatively scheduling each and
tracking the running finish time. The moment the total exceeds the current job's deadline, drop the
longest job scheduled so far — keep those lengths in a BinaryHeap (a max-heap) so the drop is
cheap. Whatever's still scheduled at the end is an optimal on-time set.
Sign in to submit your solution.