Job Sequencing with Deadlines

1from typing import NamedTuple
2 
3# Job sequencing with deadlines: each job takes one unit of time, has a
4# deadline, and pays a profit only if it finishes by then. Take jobs in
5# decreasing profit order and place each in the LATEST free slot before its
6# deadline — that placement leaves the earlier slots open for later jobs.
7 
8 
9class Job(NamedTuple):
10    deadline: int
11    profit: int
12 
13 
141 · Sort by profit, highest first
15def schedule_jobs(jobs: list[Job]) -> tuple[int, list[int]]:
16    idx = sorted(range(len(jobs)), key=lambda i: jobs[i].profit, reverse=True)
17    max_deadline = max((j.deadline for j in jobs), default=0)
18    slot = [-1] * (max_deadline + 1)  # slot[t] = job index scheduled at time t
19 
202 · For each job, scan backwards from its deadline for a free slot
21    total = 0
22    for i in idx:
23        for t in range(min(jobs[i].deadline, max_deadline), 0, -1):
24            if slot[t] == -1:
25                slot[t] = i
26                total += jobs[i].profit
27                break
28    return total, slot
29 
30 
313 · Why the LATEST free slot: filling early would consume a slot that a
32# tighter-deadline job might be the only one able to use
33def schedule_jobs_earliest_slot(jobs: list[Job]) -> int:
34    max_deadline = max((j.deadline for j in jobs), default=0)
35    used = [False] * (max_deadline + 1)
36    total = 0
37    for j in sorted(jobs, key=lambda x: x.profit, reverse=True):
38        for t in range(1, min(j.deadline, max_deadline) + 1):  # WRONG direction
39            if not used[t]:
40                used[t] = True
41                total += j.profit
42                break
43    return total  # NOT optimal — included to show the failure
44 
45 
464 · Union-find makes the slot search near-constant instead of O(deadline)
47class SlotDsu:
48    def __init__(self, n: int) -> None:
49        self.parent = list(range(n + 1))
50 
51    def find(self, x: int) -> int:
52        while self.parent[x] != x:
53            self.parent[x] = self.parent[self.parent[x]]
54            x = self.parent[x]
55        return x
56 
57 
585 · find(d) returns the latest free slot at or before d, or 0 if none
59def schedule_jobs_fast(jobs: list[Job]) -> int:
60    max_deadline = max((j.deadline for j in jobs), default=0)
61    dsu = SlotDsu(max_deadline)
62    total = 0
63    for j in sorted(jobs, key=lambda x: x.profit, reverse=True):
64        t = dsu.find(min(j.deadline, max_deadline))
65        if t > 0:
66            total += j.profit
67            dsu.parent[t] = t - 1  # that slot is now taken; point it at the previous one
68    return total