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^41 <= startTime[i] < endTime[i] <= 10^91 <= 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); }