Maximum Profit in Job Scheduling
Problem Description
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 * 104
- 1 <= startTime[i] < endTime[i] <= 109
- 1 <= profit[i] <= 104
Solve it on LeetCode
Approaches
1. Recursion with Memoization (Dynamic Programming)
Intuition:
The problem can be broken down into deciding which jobs to take to maximize the profit. For each job, you have a choice of either taking the job or skipping it. If you take the job, you cannot take any other jobs overlapping with it. Dynamic programming with memoization helps avoid recalculating results of overlapping subproblems.
Steps:
- Sort Jobs by End Time: This will allow us to process jobs in a logical order (left to right in scheduling terms).
- Use Dynamic Programming with Recursion:
- Define a recursive function
maxProfit(index)that returns the maximum profit starting from the job atindex. - Check two cases:
- Skip the current job and call
maxProfit(index + 1). - Include the current job, find the next job that can start after the current job ends using binary search, and call
maxProfit(nextIndex). - Use memoization to store and reuse results for each
index.
Code:
- Time Complexity: O(n log n) due to sorting and binary search for each job.
- Space Complexity: O(n) for the memoization array.
2. Iterative Dynamic Programming Using Sorting and Binary Search
Intuition:
Instead of using recursion, this approach uses an iterative method to build up solutions for every job from left to right. The addition of binary search helps in quickly finding the next available job that doesn't overlap with the current job.
Steps:
- Sort Jobs by End Time: Same as before, sort jobs to handle them in scheduling order.
- Dynamic Array
dp:dp[i]holds the maximum profit considering jobs up toi. - Iterate Over Each Job:
- Use binary search to find the maximum profit of the non-overlapping job.
- Update
dp[i]by comparing the addition of the current job's profit and the maximum profit of the last non-overlapping job withdp[i-1].
Code:
- Time Complexity: O(n log n) due to sorting and binary search for each job.
- Space Complexity: O(n) for maintaining the dynamic programming table.