This approach leverages sorting, dynamic programming, and binary search to solve the problem efficiently.
endTime.dp where dp[i] stores the maximum profit we can achieve by considering the first i jobs.Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the dp array.
1#include <vector>
2#include <algorithm>
3#include <map>
4
5class Solution {
6public:
7 int jobScheduling(std::vector<int>& startTime, std::vector<int>& endTime, std::vector<int>& profit) {
8 int n = startTime.size();
9 std::vector<std::array<int, 3>> jobs(n);
10 for (int i = 0; i < n; ++i) {
11 jobs[i] = {startTime[i], endTime[i], profit[i]};
12 }
13 std::sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b) {
14 return a[1] < b[1];
15 });
16 std::map<int, int> dp = {{0, 0}};
17
18 for (const auto& job : jobs) {
19 int curProfit = std::prev(dp.upper_bound(job[0]))->second + job[2];
20 if (curProfit > dp.rbegin()->second) {
21 dp[job[1]] = curProfit;
22 }
23 }
24
25 return dp.rbegin()->second;
26 }
27};This C++ solution leverages a std::map for keeping track of job end times and the maximum attained profits up to those times. Similar to other solutions, it iterates through the sorted jobs and updates the map if incorporating the current job increases the maximum profit observed so far.
The std::map is crucial here as it allows efficient searches and insertions.
This approach uses dynamic programming to solve the problem by scanning jobs and keeping track of maximum profits without the need of an auxiliary data structure for overlap checking. Instead of binary search, it uses a precomputed array to track the last non-overlapping job for each job.
endTime.Time Complexity: O(n^2) due to the nested loop search for non-overlapping jobs.
Space Complexity: O(n) for the dp array.
1function jobScheduling(startTime, endTime, profit) {
2 const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);
3 jobs.sort((a, b) => a[1] - b[1]);
4 const dp = Array(jobs.length).fill(0);
5 dp[0] = jobs[0][2];
6
7 for (let i = 1; i < jobs.length; i++) {
8 let includeProfit = jobs[i][2];
9 for (let j = i - 1; j >= 0; j--) {
10 if (jobs[j][1] <= jobs[i][0]) {
11 includeProfit += dp[j];
12 break;
13 }
14 }
15 dp[i] = Math.max(dp[i - 1], includeProfit);
16 }
17
18 return dp[dp.length - 1];
19}
20This JavaScript solution uses sorting and dynamic programming, similar to the Python solution, achieving the desired result by checking overlapping jobs through a nested loop. Profit calculations are based on conditions that evaluate to the optimal profits.