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: 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 * 104
1 <= startTime[i] < endTime[i] <= 109
1 <= profit[i] <= 104
Solution
/**
* @param {number[]} startTime
* @param {number[]} endTime
* @param {number[]} profit
* @return {number}
*/
var jobScheduling = function(startTime, endTime, profit) {
var jobs = startTime.map((_, i) => [startTime[i], endTime[i], profit[i]]);
jobs.sort((a, b) => {
return a[0] === b[0]
? (a[1] === b[1] ? a[2] - b[2] : a[1] - b[1])
: a[0] - b[0];
});
return dfs(jobs, 0, Array(jobs.length));
};
var dfs = function(jobs, i, dp) {
if (i === jobs.length) return 0;
if (dp[i] !== undefined) return dp[i];
dp[i] = Math.max(
// take job i
jobs[i][2] + dfs(jobs, next(i, jobs), dp),
// do not take job i
dfs(jobs, i + 1, dp),
);
return dp[i];
};
var next = function(i, jobs) {
// binary search job j which starts after job i ends.
var left = 0;
var right = jobs.length - 1;
while (left < right) {
var mid = left + Math.floor((right - left) / 2);
if (jobs[i][1] > jobs[mid][0]) {
left = mid + 1;
} else {
right = mid;
}
}
return jobs[i][1] <= jobs[left][0] ? left : jobs.length;
};
Explain:
nope.
Complexity:
- Time complexity : O(n * log(n)).
- Space complexity : O(n).