Maximum Profit in Job Scheduling
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 are given the startTime, endTime, and profit arrays. Return the maximum profit you can take such that there are no two jobs in the chosen subset with overlapping time ranges.
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
120The subset chosen is the first and fourth job, giving profit 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
150The subset chosen is the first, fourth, and fifth job, giving profit 150 = 20 + 70 + 60.
Constraints
- 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
- 1 <= startTime[i] < endTime[i] <= 10^9
- 1 <= profit[i] <= 10^4
Asked at 25 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.