Maximum Profit in Job Scheduling

The key idea

Sort jobs by end time, then build dp where dp[i] is the best profit achievable considering the first i jobs in that order. For each job you make a binary choice: skip it (carry dp[i-1]) or take it (its profit plus the best dp value of all jobs that finish at or before this job starts). A binary search finds that latest compatible job in O(log n), so the whole scan is O(n log n).

Problem

You are given n jobs, where every job is described by three arrays startTime, endTime, and profit. Job i starts at startTime[i], finishes at endTime[i], and pays you profit[i].

Pick a subset of jobs so that no two chosen jobs overlap in time, and the total profit is as large as possible. Return this maximum profit.

If a job ends at time X, you are allowed to start another job at the same time X (the half-open intervals [startTime[i], endTime[i]) may touch but must not overlap).

Constraints

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Examples

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6

Complexity

Time: O(n log n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →