forked from Arunav07/dsc-hacktoberfest-2021
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Max Profit in job scheduling
50 lines (48 loc) · 1.95 KB
/
Max Profit in job scheduling
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
First,create job class such that each instance of a job has a start time,an end time and a profit;
class Job:
def _init_(self, start, finish, profit):
self.start = start
self.finish = finish
self.profit = profit
Next from our input arrays let's create jon instances based on ending times:
def solution(startTime, endTime, profit) -> int:
jobs = []
for i in range(len(profit)):
jobs.append(Job(startTime[i], endTime[i], profit[i]))
# sort jobs in increasing order of their finish times
jobs.sort(key=lambda x: x.finish)
Ater that we take our usual bottom up approach:
# initialize max profit table
maxProfit = [0 for i in range(len(jobs))]
maxProfit[0] = jobs[0].profit
for i in range(1, len(jobs)):
# find the index of last non-conflicting job with current job
# j = -1 if no index could be found
j = get_last_non_conflicting_job(jobs, i)
# include the current job with its non-conflicting job
profit = jobs[i].profit
if j != -1:
profit += maxProfit[j]
# store the maximum profit by including or excluding the current job
maxProfit[i] = max(profit, maxProfit[i-1])
return maxProfit[len(jobs) - 1]
To get our last non-conflicting job,we can do a simple linera search:-
def get_last_non_conflicting_job(jobs, n):
for i in reversed(range(n)):
if jobs[i].finish <= jobs[n].start:
return i
return -1 # if no non-conflicting job is found
Our linear search can be optimised further using a binary search:-
def get_last_non_conflicting_job(jobs, n):
low = 0
high = n
while low <= high:
mid = (low + high) // 2
if jobs[mid].finish <= jobs[n].start:
if jobs[mid + 1].finish <= jobs[n].start:
low = mid + 1
else:
return mid
else:
high = mid - 1
return -1 # if no non-conflicting job is found