MUYANG GUO / INDEX

LeetCode

LeetCode 1235 Maximum Profit In Job Scheduling - Hard

1235. Maximum Profit in Job Scheduling -- Hard

·2 min read·#LeetCode#Hard#Python

1235. Maximum Profit In Job Scheduling — Hard

Open on LeetCode

Problem

  1. Maximum Profit in Job Scheduling -- Hard

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

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4 1 <= startTime[i] < endTime[i] <= 10^9 1 <= profit[i] <= 10^4

Solution

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        #each job = [s, e, p], where s,e,p are its start time, end time and profit,
        #If we don't do this job, nothing will be changed.
        #If do the job, binary search in the dp to find the largest profit we can make before start time s.
        #So we also know the maximum current profit that we can make doing this j
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
        dp = [[0, 0]]
        for s, e, p in jobs:
            i = bisect.bisect(dp, [s + 1]) - 1
            if dp[i][1] + p > dp[-1][1]:
                dp.append([e, dp[i][1] + p])
        return dp[-1][1]

Comments