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.
1def jobScheduling(startTime, endTime, profit):
2 jobs = list(zip(startTime, endTime, profit))
3 jobs.sort(key=lambda x: x[1])
4 n = len(jobs)
5 dp = [0] * n
6 dp[0] = jobs[0][2]
7
8 for i in range(1, n):
9 # Include the current job
10 includeProfit = jobs[i][2]
11 l = 0
12 for j in range(i - 1, -1, -1):
13 if jobs[j][1] <= jobs[i][0]:
14 includeProfit += dp[j]
15 break
16
17 dp[i] = max(includeProfit, dp[i - 1])
18
19 return dp[-1]
The Python solution sorts jobs by endTime
and iterates through each job, computing the maximum profit by considering two cases: including or excluding the current job. It utilizes a nested loop to find the last non-overlapping job in an optimized way, considering constraints on input sizes.