-
Notifications
You must be signed in to change notification settings - Fork 47
/
jobseq.py
62 lines (41 loc) · 1.48 KB
/
jobseq.py
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
import heapq
def printJobScheduling(arr):
n = len(arr)
# arr[i][0] = job_id, arr[i][1] = deadline, arr[i][2] = profit
# sorting the array on the
# basis of their deadlines
arr.sort(key=lambda x: x[1])
# initialise the result array and maxHeap
result = []
maxHeap = []
# starting the iteration from the end
for i in range(n - 1, -1, -1):
# calculate slots between two deadlines
if i == 0:
slots_available = arr[i][1]
else:
slots_available = arr[i][1] - arr[i - 1][1]
# include the profit of job(as priority), deadline
# and job_id in maxHeap
# note we push negative value in maxHeap to convert
# min heap to max heap in python
heapq.heappush(maxHeap, (-arr[i][2], arr[i][1], arr[i][0]))
while slots_available and maxHeap:
# get the job with max_profit
profit, deadline, job_id = heapq.heappop(maxHeap)
# reduce the slots
slots_available -= 1
# include the job in the result array
result.append([job_id, deadline])
result.sort(key=lambda x: x[1])
for job in result:
print(job[0], end=" ")
print()
if __name__ == '__main__':
arr = [['a', 2, 100],
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]
print("Following is maximum profit sequence of jobs")
printJobScheduling(arr)