Loading problem…
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
Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: Take job 0 ([1,3], profit 50) and job 3 ([3,6], profit 70). A job may start when another ends, so they fit together, for a total of 120.
Example 2
Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: Take the jobs [1,3] (20), [4,6] (70) and [6,9] (60) for 150. The single big job [3,10] (100) only pairs with [1,3] for a total of 120.
Example 3
Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6
Explanation: All three jobs start at time 1, so they all overlap and only one can be picked. The best is the job worth 6.
Sort jobs by end time. For each job, the best profit is either skipping it, or taking it plus the best profit among jobs that finish by its start — found with binary search.
Run checks all cases above. Submit evaluates all test cases.