Minimize Late Jobs (Go)
Topics: scheduling, greedy, max-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 — pick
the subset and order that lands the most jobs on or before their deadlines.
type Job struct { Length, Deadline int }
func MaxOnTime(jobs []Job) int
- Return the maximum count of jobs that complete by their deadline.
- Jobs you don't pick are dropped; you choose both the set and the order.
MaxOnTime must not mutate the input slice, and the answer can't 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 — it frees the most time for the fewest losses. Keep the dropped
lengths in a max-heap. Whatever's still scheduled at the end is an optimal on-time set.
Sign in to submit your solution.