forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjob_scheduling.py
More file actions
79 lines (57 loc) · 1.82 KB
/
job_scheduling.py
File metadata and controls
79 lines (57 loc) · 1.82 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""
Weighted Job Scheduling
Given a set of jobs with start times, finish times, and profits, find
the maximum profit subset such that no two jobs overlap.
Reference: https://en.wikipedia.org/wiki/Job-shop_scheduling
Complexity:
Time: O(n^2)
Space: O(n)
"""
from __future__ import annotations
class Job:
"""Represents a job with start time, finish time, and profit."""
def __init__(self, start: int, finish: int, profit: int) -> None:
self.start = start
self.finish = finish
self.profit = profit
def _binary_search(job: list[Job], start_index: int) -> int:
"""Find the latest non-conflicting job before start_index.
Args:
job: List of jobs sorted by finish time.
start_index: Index of the current job.
Returns:
Index of the latest compatible job, or -1 if none exists.
"""
left = 0
right = start_index - 1
while left <= right:
mid = (left + right) // 2
if job[mid].finish <= job[start_index].start:
if job[mid + 1].finish <= job[start_index].start:
left = mid + 1
else:
return mid
else:
right = mid - 1
return -1
def schedule(job: list[Job]) -> int:
"""Find the maximum profit from non-overlapping jobs.
Args:
job: List of Job objects.
Returns:
Maximum achievable profit.
Examples:
>>> schedule([Job(1, 3, 2), Job(2, 3, 4)])
4
"""
job = sorted(job, key=lambda j: j.finish)
length = len(job)
table = [0 for _ in range(length)]
table[0] = job[0].profit
for i in range(1, length):
incl_prof = job[i].profit
pos = _binary_search(job, i)
if pos != -1:
incl_prof += table[pos]
table[i] = max(incl_prof, table[i - 1])
return table[length - 1]