Watch 10 video solutions for Maximum Profit in Job Scheduling, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by NeetCodeIO has 55,650 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 1041 <= startTime[i] < endTime[i] <= 1091 <= profit[i] <= 104Problem Overview: You receive three arrays representing job startTime, endTime, and profit. Each job must finish before another begins. The goal is to select a subset of non-overlapping jobs that produces the maximum total profit.
Approach 1: Dynamic Programming with Binary Search (O(n log n) time, O(n) space)
Start by combining the inputs into job tuples and sorting them by startTime (or endTime). The key idea is to treat this as a weighted interval scheduling problem. For each job, you decide whether to skip it or take it and jump to the next non-overlapping job. Instead of scanning linearly to find that next job, use binary search on the sorted start times to locate the first job whose start time is greater than or equal to the current jobβs end time.
Define a dp[i] value representing the maximum profit achievable starting from job i. The transition becomes dp[i] = max(dp[i+1], profit[i] + dp[nextIndex]), where nextIndex is found using binary search. Sorting plus binary search reduces the transition lookup from O(n) to O(log n), giving an overall time complexity of O(n log n). This approach relies heavily on Sorting, Binary Search, and Dynamic Programming. It scales well to large job lists and is the standard optimal solution.
Approach 2: Dynamic Programming with Linear Scan (O(n^2) time, O(n) space)
This version keeps the same dynamic programming idea but replaces the binary search step with a linear scan. After sorting jobs by start time, iterate through the remaining jobs to find the next job that starts after the current job ends. The recurrence is identical: choose the maximum between skipping the current job or taking its profit and adding the result from the next compatible job.
The implementation is straightforward because it avoids binary search and extra indexing structures. However, the search for the next valid job may take up to O(n) time for each state, producing a total time complexity of O(n^2). Space complexity remains O(n) for the DP array. This approach works well when input sizes are small or when you want a simpler baseline solution before optimizing.
Recommended for interviews: The expected solution is dynamic programming with binary search. It demonstrates understanding of weighted interval scheduling and shows you can optimize DP transitions using sorted structures. Starting with the linear scan version can help explain the intuition, but converting the lookup to binary search is what interviewers typically want to see.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Binary Search | O(n log n) | O(n) | Best general solution for large inputs. Efficiently finds the next compatible job using binary search. |
| Dynamic Programming with Linear Scan | O(n^2) | O(n) | Simpler implementation. Useful for understanding the DP transition before optimizing. |
| Brute Force Recursion | O(2^n) | O(n) | Conceptual baseline that tries every subset of jobs. Quickly becomes impractical for large n. |