Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1235.html
1235. 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
Related Topics: Binary Search, Dynamic Programming, Sort
Solution 1. DP + Binary Search
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int N = startTime.size();
vector<vector<int>> v(N, vector<int>(3));
for (int i = 0; i < N; ++i) {
v[i][0] = startTime[i];
v[i][1] = endTime[i];
v[i][2] = profit[i];
}
sort(v.begin(), v.end()); // sort in asending order of start time.
vector<int> dp(N + 1);
for (int i = N - 1; i >= 0; --i) {
dp[i] = dp[i + 1]; // roll the max profit over
int e = v[i][1];
vector<int> c{ e, e, 0 }; // find the first job whose startTime is greater than or equal to the end time of the current job
int j = lower_bound(v.begin(), v.end(), c) - v.begin(); // `upper_bound` also works because it's impossible to be equal to the job `e, e, 0`.
dp[i] = max(dp[i], dp[j] + v[i][2]);
}
return dp[0];
}
};
Or
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/409188/C%2B%2B-with-picture
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
map<int, int> maxProfit; // start time to max profit
unordered_map<int, vector<pair<int, int>>> jobs; // start time to <endTime, profit>
for (int i = 0; i < startTime.size(); ++i) {
maxProfit[startTime[i]] = 0;
jobs[startTime[i]].emplace_back(endTime[i], profit[i]);
}
int ans = 0;
for (auto it = rbegin(maxProfit); it != rend(maxProfit); ++it) {
for (auto &job : jobs[it->first]) {
auto j = maxProfit.lower_bound(job.first); // find the first job whose start time is greater than or equal to the end time of this current job.
ans = max(ans, (j == end(maxProfit) ? 0 : j->second) + job.second);
}
it->second = ans;
}
return ans;
}
};
Using the ID array idx
saves space compared to saving endTime
and profit
in another map
as shown in the above solutions.
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/409188/C%2B%2B-with-picture
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
vector<int> idx(startTime.size());
iota(begin(idx), end(idx), 0);
sort(begin(idx), end(idx), [&](int i, int j) { return startTime[i] > startTime[j]; }); // sort the job ids in descending order of start time.
map<int, int> maxProfit; // start time to max profit
int ans = 0;
for (int i = 0; i < idx.size(); ++i) {
auto j = maxProfit.lower_bound(endTime[idx[i]]); // find the first job whose start time is greater than or equal to the end time of the current job.
ans = max(ans, (j == end(maxProfit) ? 0 : j->second) + profit[idx[i]]);
maxProfit[startTime[idx[i]]] = ans;
}
return ans;
}
};
Solution 1. DP + Binary Search
For a job with startTime s
, endTime e
, and profit p
, we need look at all the jobs ends at and before s
.
Let dp[s]
be the maximum profit we can get from the beginning to time s
, then we can try to update dp[e]
with dp[s] + p
.
But dp[s]
is not necessarily set because there might be no jobs ending at s
, so we need to find the maximum time t <= s
, and use dp[t]
.
To achieve this, we can keep the dp
values sorted in ascending order of the key, i.e. time.
To ensure we’ve visited all the jobs ends before startTime s
, we sort the jobs in ascending order of endTime
.
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
vector<array<int, 3>> jobs;
for (int i = 0; i < startTime.size(); ++i) jobs.push_back({ endTime[i], startTime[i], profit[i] });
sort(begin(jobs), end(jobs));
map<int, int> dp{ {0, 0} }; // endTime to max profit
int ans = 0;
for (auto &[e, s, p] : jobs) {
dp[e] = max(ans, p + prev(dp.upper_bound(s))->second);
ans = max(ans, dp[e]);
}
return ans;
}
};
Or
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int ans = 0, N = startTime.size();
vector<array<int, 3>> jobs(N + 1);
for (int i = 0; i < N; ++i) jobs[i + 1] = { endTime[i], startTime[i], profit[i] };
sort(begin(jobs), end(jobs));
vector<int> dp(N + 1);
for (int i = 1; i <= N; ++i) {
auto [e, s, p] = jobs[i];
int j = prev(upper_bound(begin(jobs), end(jobs), array<int, 3>{s, s, 0})) - begin(jobs);
dp[i] = max(ans, p + dp[j]);
ans = max(ans, dp[i]);
}
return ans;
}
};
Another way to get the upper_bound
is as follows
upper_bound(begin(jobs), end(jobs), s, [](int a, auto &b) { return a < b[0]; })
Solution 2. DP + Binary Search
The other way around also works, i.e. sorting the jobs based on the start times and get the dp
values in descending order of time.
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
vector<array<int, 3>> jobs;
for (int i = 0; i < startTime.size(); ++i) jobs.push_back({ startTime[i], endTime[i], profit[i] });
sort(begin(jobs), end(jobs), greater<>());
map<int, int> dp{ {INT_MAX, 0} }; // startTime to max profit
int ans = 0;
for (auto &[s, e, p] : jobs) {
dp[s] = max(ans, p + dp.lower_bound(e)->second);
ans = max(ans, dp[s]);
}
return ans;
}
};
Or
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int ans = 0, N = startTime.size();
vector<array<int, 3>> jobs(N + 1);
jobs[N] = { INT_MAX, INT_MAX, 0 };
for (int i = 0; i < N; ++i) jobs[i] = { startTime[i], endTime[i], profit[i] };
sort(begin(jobs), end(jobs));
vector<int> dp(N + 1);
for (int i = N - 1; i >= 0; --i) {
auto [s, e, p] = jobs[i];
int j = lower_bound(begin(jobs), end(jobs), array<int, 3>{e, e, 0}) - begin(jobs);
dp[i] = max(ans, p + dp[j]);
ans = max(ans, dp[i]);
}
return ans;
}
};
-
class Solution { public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int length = startTime.length; int[][] jobs = new int[length][3]; for (int i = 0; i < length; i++) { jobs[i][0] = startTime[i]; jobs[i][1] = endTime[i]; jobs[i][2] = profit[i]; } Arrays.sort(jobs, new Comparator<int[]>() { public int compare(int[] job1, int[] job2) { return job1[1] - job2[1]; } }); int[] prevJobs = new int[length]; for (int i = 0; i < length; i++) prevJobs[i] = binarySearch(jobs, jobs[i][0]); int[][] dp = new int[length][2]; dp[0][0] = 0; dp[0][1] = jobs[0][2]; for (int i = 1; i < length; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]); int prevJob = prevJobs[i]; if (prevJob >= 0) dp[i][1] = Math.max(dp[prevJob][0], dp[prevJob][1]) + jobs[i][2]; else dp[i][1] = jobs[i][2]; } return Math.max(dp[length - 1][0], dp[length - 1][1]); } public int binarySearch(int[][] jobs, int maxEndTime) { int low = 0, high = jobs.length - 1; while (low <= high) { int mid = (high - low + 1) / 2 + low; int[] job = jobs[mid]; if (job[1] > maxEndTime) high = mid - 1; else { if (low == high) break; else low = mid; } } return high; } } ############ class Solution { public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n = profit.length; int[][] jobs = new int[n][3]; for (int i = 0; i < n; ++i) { jobs[i] = new int[] {startTime[i], endTime[i], profit[i]}; } Arrays.sort(jobs, (a, b) -> a[1] - b[1]); int[] dp = new int[n + 1]; for (int i = 0; i < n; ++i) { int j = search(jobs, jobs[i][0], i); dp[i + 1] = Math.max(dp[i], dp[j] + jobs[i][2]); } return dp[n]; } private int search(int[][] jobs, int x, int n) { int left = 0, right = n; while (left < right) { int mid = (left + right) >> 1; if (jobs[mid][1] > x) { right = mid; } else { left = mid + 1; } } return left; } }
-
// OJ: https://leetcode.com/problems/maximum-profit-in-job-scheduling/ // Time: O(NlogN) // Space: O(N) class Solution { public: int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) { vector<array<int, 3>> jobs; for (int i = 0; i < startTime.size(); ++i) jobs.push_back({ startTime[i], endTime[i], profit[i] }); sort(begin(jobs), end(jobs), greater<>()); // sort jobs in descending order of start time map<int, int> dp{ {INT_MAX, 0} }; // startTime to max profit int ans = 0; for (auto &[s, e, p] : jobs) { dp[s] = max(ans, p + dp.lower_bound(e)->second); ans = max(ans, dp[s]); } return ans; } };
-
class Solution: def jobScheduling( self, startTime: List[int], endTime: List[int], profit: List[int] ) -> int: jobs = sorted(zip(endTime, startTime, profit)) n = len(profit) dp = [0] * (n + 1) for i, (_, s, p) in enumerate(jobs): j = bisect_right(jobs, s, hi=i, key=lambda x: x[0]) dp[i + 1] = max(dp[i], dp[j] + p) return dp[n]
-
func jobScheduling(startTime []int, endTime []int, profit []int) int { n := len(profit) type tuple struct{ s, e, p int } jobs := make([]tuple, n) for i, p := range profit { jobs[i] = tuple{startTime[i], endTime[i], p} } sort.Slice(jobs, func(i, j int) bool { return jobs[i].e < jobs[j].e }) dp := make([]int, n+1) for i, job := range jobs { j := sort.Search(i, func(k int) bool { return jobs[k].e > job.s }) dp[i+1] = max(dp[i], dp[j]+job.p) } return dp[n] } func max(a, b int) int { if a > b { return a } return b }
-
function jobScheduling( startTime: number[], endTime: number[], profit: number[], ): number { const n = startTime.length; const f = new Array(n).fill(0); const idx = new Array(n).fill(0).map((_, i) => i); idx.sort((i, j) => startTime[i] - startTime[j]); const search = (x: number) => { let l = 0; let r = n; while (l < r) { const mid = (l + r) >> 1; if (startTime[idx[mid]] >= x) { r = mid; } else { l = mid + 1; } } return l; }; const dfs = (i: number): number => { if (i >= n) { return 0; } if (f[i] !== 0) { return f[i]; } const j = search(endTime[idx[i]]); return (f[i] = Math.max(dfs(i + 1), dfs(j) + profit[idx[i]])); }; return dfs(0); }