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.
1from bisect import bisect_right
2
3def jobScheduling(startTime, endTime, profit):
4 jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
5 end_times = [job[1] for job in jobs]
6 dp = [0] * (len(jobs) + 1)
7
8 for i in range(1, len(jobs) + 1):
9 k = bisect_right(end_times, jobs[i-1][0])
10 dp[i] = max(dp[i-1], jobs[i-1][2] + dp[k])
11
12 return dp[-1]The solution begins by sorting the jobs in increasing order of their end times. This allows us to consider each job and decide whether to include it based on the results of previously solved subproblems stored in the dp array.
For each job, we perform a binary search using bisect_right to find the index of the last job that doesn't conflict with the current one, and update the maximum profit accordingly.
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,
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.
This 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.