Module 13 · Greedy · Greedy Approach

Job sequencing problem

Take the jobs from the highest profit down. Each one gets the latest free day on or before its deadline: doing it as late as allowed keeps the earlier days free for jobs that are due sooner. A job with every day up to its deadline taken is dropped.

The latest free day comes from a disjoint set, SlotManager: find(d) follows parent from day d down to the latest free day at or before it (0 means none), and points every day on that path straight at the answer. occupySlot(d) links a used day to the free day before it.

jobs shows each job's profit, with its name and deadline under it, in the order they are tried. parent is the slot manager's array for days 0 to the latest deadline; days shows which job each day holds.