# 1235. Maximum Profit in Job Scheduling
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].
You're given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.
If you choose a job that ends at time X you will be able to start another job that starts at time X.
Example 1:
Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job.
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.
Example 2:
Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.
Example 3:
Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6
# Solution
Approach 1: (TLE) knapsack. Sort the jobs by start time, and let total[i][j]
to be the max total profit using first i items up until time j.
Approach 2: (TLE) typical 2D array setup -- let table[i][j]
be the max profit starting time i and ending time j.
Approach 3: monotonic time flow + binary search. Keep a list of (time_consumed_to_reach_this_max_profit, max_profit_value)
, and for each job, try to add to this list if doing this job yields higher profit. Time: O(NlogN)
.
# Code (Python)
Approach 1:
def jobScheduling(self, start_time, end_time, profit):
# total[i][j]: max total profit using first i items up until time j
# init: total[0][j] = 0, total[i][0] = 0
# transfer: total[i][j] = max(total[i-1][j], total[i][j-1], profit[i-1] + total[i-1][start[i-1]] if end[j] <= j)
# time: O(max(len of jobs * max end time, JlogJ -- J for len of jobs)) TLE
jobs = sorted(zip(start_time, end_time, profit))
total = [[0] * (max(end_time) + 1) for _ in range(len(jobs) + 1)]
for i in range(1, len(total)):
for j in range(1, len(total[0])):
total[i][j] = max(total[i-1][j], total[i][j-1])
if jobs[i-1][1] <= j:
total[i][j] = max(total[i][j], jobs[i-1][2] + total[i-1][jobs[i-1][0]])
return max(total[-1])
Approach 2:
from collections import defaultdict
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
table = defaultdict(int)
for i in range(len(startTime)):
table[(startTime[i], endTime[i])] = profit[i]
min_start, max_end = min(startTime), max(endTime)
for delta in range(1, max_end - min_start + 2):
start = min_start
while True:
end = start + delta
max_val = 0
if end <= max_end:
for i in range(start, end + 1):
max_val = max(max_val, table[(start, i)] + table[(i, end)])
table[(start, end)] = max_val
else:
break
start += 1
return table[(min_start, max_end)]
Approach 3:
import bisect
class Solution:
def jobScheduling(self, start_time, end_time, profit):
# https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/409009/JavaC%2B%2BPython-DP-Solution
# time progresses monotonically. keep a list of (time_consumed_to_reach_this_max_profit, max_profit_value)
# for each job, try to add to this list if doing this job yields higher profit
jobs = sorted(zip(start_time, end_time, profit), key=lambda job: job[1])
max_profit = [[0,0]]
for job in jobs:
# search max profit before this job starts, in order to replace the later ones
index = bisect.bisect_right(max_profit, [job[0], float('inf')]) - 1 # bisect_left doesn't work because not sure whether it returns that index or next
if max_profit[index][1] + job[2] > max_profit[-1][1]:
max_profit.append([job[1], max_profit[index][1] + job[2]])
return max_profit[-1][-1]
# Code (C++)
Approach 1:
Approach 2: