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 * 1041 <= startTime[i] < endTime[i] <= 1091 <= profit[i] <= 104Maximum Profit in Job Scheduling is a classic variation of the Weighted Interval Scheduling problem. Each job has a start time, end time, and profit, and the goal is to select a set of non-overlapping jobs that maximizes total profit.
A common strategy begins by sorting jobs by their end time. After sorting, you can use Dynamic Programming where dp[i] represents the maximum profit achievable considering jobs up to index i. For each job, you decide whether to skip it or include it and add its profit to the best compatible job that finishes before its start time.
To efficiently find the last non-conflicting job, apply Binary Search on the sorted end times. This reduces the search from linear to logarithmic time. The combination of sorting, DP, and binary search leads to an efficient solution.
The overall complexity is typically O(n log n) due to sorting and binary searches, while the DP array requires O(n) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Binary Search | O(n log n) | O(n) |
| DP with Linear Scan for Previous Job | O(n^2) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Think on DP.
Sort the elements by starting time, then define the dp[i] as the maximum profit taking elements from the suffix starting at i.
Use binarySearch (lower_bound/upper_bound on C++) to get the next index for the DP transition.
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,
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting jobs by their end time allows you to process them in a logical order and efficiently determine which previous job does not conflict. This ordering enables the DP transition and binary search optimization.
Yes, this problem is a well-known variation of weighted interval scheduling and is frequently discussed in technical interviews at companies like Google, Amazon, and Meta. It tests dynamic programming and binary search skills.
Arrays or lists are typically used to store jobs and the DP states. Binary search on a sorted array of job end times helps quickly locate the last compatible job.
The optimal approach combines sorting, dynamic programming, and binary search. After sorting jobs by end time, DP tracks the best profit up to each job, while binary search finds the last non-overlapping job efficiently.
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.