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] <= 104This 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.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.
Java
C++
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the dp array.
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.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.
JavaScript
Time Complexity: O(n^2) due to the nested loop search for non-overlapping jobs.
Space Complexity: O(n) for the dp array.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: |
| Dynamic Programming With Linear Scan | Time Complexity: |
Maximum Profit in Job Scheduling - Leetcode 1235 - Python • NeetCodeIO • 41,292 views views
Watch 9 more video solutions →Practice Maximum Profit in Job Scheduling with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor