Maximum Profit in Job Scheduling
Hard · 2-D Dynamic Programming · Array · Binary Search · Dynamic Programming · Sorting
Problem
You have n jobs. Job i runs from startTime[i] to endTime[i] and pays profit[i]. The three arrays have equal length.
Choose a set of jobs with no overlapping time ranges and return the largest total profit you can earn. A job that ends at time X does not conflict with a job that starts at time X.
Examples
Input: startTime = [1,2,4,6], endTime = [3,5,6,9], profit = [20,30,25,40] Output: 85
Take jobs 1, 3 and 4 (times 1–3, 4–6, 6–9) for 20 + 25 + 40.
Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6
All jobs overlap at time 1, so pick the single most profitable one.
Input: startTime = [1,3], endTime = [3,5], profit = [10,10] Output: 20
The first job ends exactly when the second starts, so both are allowed.
Constraints
- 1 <= n <= 5 · 10^4
- n == len(startTime) == len(endTime) == len(profit)
- 1 <= startTime[i] < endTime[i] <= 10^9
- 1 <= profit[i] <= 10^4
Approaches
- Sort by end, DP with a backward scan — time O(n²), space O(n)
Follow-up
If every job paid the same, the DP would be unnecessary: taking the job that ends first, again and again, is optimal. If you could take at most k jobs, add the job count as a second dimension: dp[c][i], for O(n log n + n · k).
Related problems
Start free on Cariara · Coding problems · System design studio
