## # 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: monotonic time flow + binary search. Keep a list of `(this_max_profit_start_at_time, 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[j] = 0, total[i] = 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 = [ * (max(end_time) + 1) for _ in range(len(jobs) + 1)]
for i in range(1, len(total)):
for j in range(1, len(total)):
total[i][j] = max(total[i-1][j], total[i][j-1])
if jobs[i-1] <= j:
total[i][j] = max(total[i][j], jobs[i-1] + total[i-1][jobs[i-1]])
return max(total[-1])
``````

Approach 2:

``````import bisect
class Solution:
def jobScheduling(self, start_time, end_time, profit):
# time progresses monotonically. keep a list of (this_max_profit_start_at_time, 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)
max_profit = [[0,0]]
for job in jobs:
# search max profit when this job starts, in order to replace the later ones
index = bisect.bisect_right(max_profit, [job, float('inf')]) - 1 # bisect_left doesn't work because not sure whether it returns that index or next
if max_profit[index] + job > max_profit[-1]:
max_profit.append([job, max_profit[index] + job])

return max_profit[-1][-1]
``````

Approach 1:

Approach 2: