Problem description:

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, return the maximum profit you can take such that there are no two 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:

https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png

1
2
3
4
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:

https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png

1
2
3
4
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:

https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png

1
2
Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
  • 1 <= startTime[i] < endTime[i] <= 109
  • 1 <= profit[i] <= 104

Solution:

If we sort jobs by start time, starting from job index cur = 0, we might either schedule the jobs[cur] or not.

  • If we schedule jobs[cur], the problem becomes profit of jobs[cur] + max profit of scheduling jobs starting from next available job index.
  • If we don’t schedule jobs[cur], earn 0 profit for current job, the problem becomes max profit of scheduling jobs starting from cur + 1.

We choose the one giving more profits.

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
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        tasks = sorted(zip(startTime, endTime, profit), key = lambda v:v[0])
        print(tasks)
        dp = defaultdict()
        
        def helper(jobid):
            # calculate the max profit for each job
            # 1. take jobid: profit become jobid's profit + followup dp jobs
            # 2. not take job: find another job 
            if jobid in dp:
                return dp[jobid]
            if jobid == -1 or jobid >= len(tasks):
                return 0
            nextJob = findNext(jobid)
            
            acceptJob = tasks[jobid][2]+ helper(nextJob)
            declineJob = helper(jobid+1)
            dp[jobid] = max(acceptJob, declineJob)
            return dp[jobid]
        
        def findNext(jobid):
            if jobid >= len(tasks) or tasks[-1][0] < tasks[jobid][1]:
                # last one start time has passed jodid's end time
                return -1
            l, r, target = jobid, len(tasks)-1, tasks[jobid][1]
            while l < r:
                mid = (l+r) //2
                if tasks[mid][0] >= target: 
                    # task mid can be scheduled after jobid ends
                    r = mid
                else:
                    l = mid+1
            return r # which job should take
        return helper(0)

time complexity: $O()$
space complexity: $O()$
reference:
related problem:

Follow up

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
from collections import defaultdict
class Solution:
    def jobScheduling(self, startTime, endTime, profit, start, end):
        # use top-down dp
        # if start a job, then the following max profit should be the same
        # for every job's max profit:
        # 1. curJob.profit + dfs(nextJob)
        # 2. dfs(nextJob)
        
        # when find next, use binary search to get a job 
        # next job should start after curJob.endTime
        
        
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[0])
        i = 0
        while i < len(jobs):
            if jobs[i][0] < start or jobs[i][1] > end:
                jobs = jobs[:i] + jobs[i + 1:]
            else:
                i += 1
        
        print(jobs)
                
        dp = defaultdict()
        
        def helper(curJob):
            if curJob in dp:
                return dp[curJob]
            if curJob == -1 or curJob >= len(jobs):
                return 0
            
            nextJob = findNext(curJob)
            acceptJob = jobs[curJob][2] + helper(nextJob)
            declineJob = helper(curJob+1)
            dp[curJob] = max(acceptJob, declineJob)
            return dp[curJob]
        
        def findNext(curJob):
            if curJob >= len(jobs) or jobs[-1][0] < jobs[curJob][1]:
                return -1
            l, r = curJob, len(jobs)-1
            target = jobs[curJob][1]
            
            while l < r:
                mid = (l+r) //2 
                if jobs[mid][0] >= target:
                    r = mid
                else:
                    l = mid +1
            return r
        return helper(0)

solution = Solution()
startTime = [1,2,3,3]
endTime = [3,4,5,6]
profit = [50,10,40,70]
res = solution.jobScheduling(startTime, endTime, profit, 1, 5)
print(res)