Maximum Profit in Job Scheduling
Adobe
PhonePeThe problem
You are given n jobs, where every job is represented by:
- startTime[i]: the start time of the job,
- endTime[i]: the end time of the job,
- profit[i]: the profit earned from completing the job.
You cannot take two jobs that overlap in time.
Return the maximum profit you can earn such that there are no two overlapping jobs in your selected subset.
Note: A job ending at time X is allowed to overlap with another job that starts exactly at time X.
Input: startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70] **Output: **120 Explanation:
- Select jobs [0, 3] with intervals [1-3] and [3-6].
- Profit = 50 + 70 = 120.
**Input: **startTime = [1, 2, 3, 4, 6], endTime = [3, 5, 10, 6, 9], profit = [20, 20, 100, 70, 60] **Output: **150 Explanation:
- Select jobs [0, 3, 4]: [1-3], [4-6], [6-9]
- Total profit = 20 + 70 + 60 = 150.
Input: startTime = [1, 1, 1], endTime = [2, 3, 4], profit = [5, 6, 4]
- 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
- 1 <= startTime[i] < endTime[i] <= 109
- 1 <= profit[i] <= 104
cpp
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
// Your code goes here
}
};java
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
// Your code goes here
}
}python
class Solution:
def jobScheduling(self, startTime, endTime, profit):
# Your code goes herejavascript
function jobScheduling(startTime, endTime, profit) {
// Your code goes here
}csharp
class Solution {
public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
// Your code goes here
}
}go
func jobScheduling(startTime []int, endTime []int, profit []int) int {Stuck? Show a way to structure it+
- 01Sort jobs by end time.
- 02Define dp[i] as best profit through i jobs.
- 03Binary-search the last compatible earlier job.
- 04Choose between skipping or taking the current job.
- 05Return the final DP value.
Reference answer
Then expect these follow-ups
How would you reconstruct selected jobs?
Tests: DP reconstruction
Can you use recursion with memoization?
Tests: equivalent formulations
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question