Maximum Profit in Job Scheduling solution and explanation
Infosys
Google
9 more videos on this problem
Maximum Profit in Job Scheduling - Leetcode 1235 - PythonNeetCodeIO · 14:45 · 58K views
Maximum Profit in Job Scheduling | Recursion | Memoization | Leetcode 1235codestorywithMIK · 27:50 · 36K views
Maximum Profit in Job Scheduling | Live Coding with Explanation | Leetcode - 1235Algorithms Made Easy · 13:33 · 35K views
LeetCode 1235. Maximum Profit in Job SchedulingHappy Coding · 30:47 · 12K views
Leetcode - Maximum Profit in Job Scheduling (Python)Timothy H Chang · 7:20 · 10K views
1235. Maximum Profit in Job Scheduling | DP | Binary SearchAryan Mittal · 17:50 · 9K views
Daily Leetcode #970: Nov 26, 2022 - 1235. Maximum Profit in Job SchedulingProgramming Live with Larry · 11:19 · 1K views
Daily Leetcode #1376: Jan 06, 2024 - 1235. Maximum Profit in Job SchedulingProgramming Live with Larry · 10:40 · 754 views
Maximum Profit in Job Scheduling Leetcode 1235 || Coding Culture5 Minutes Code · 13:05 · 740 views
Daily Leetcode #515: Aug 28, 2021 - 1235. Maximum Profit in Job SchedulingProgramming Live with Larry · 18:02 · 601 views
The problem
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] <= 104
Approach overview
Problem 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 1: Dynamic Programming with Binary Search
This approach leverages sorting, dynamic programming, and binary search to solve the problem efficiently.
- Sort the jobs based on their
endTime. - Use a dynamic programming array
dpwheredp[i]stores the maximum profit we can achieve by considering the firstijobs. - For each job, find the most recent non-conflicting job using binary search.
- Calculate the maximum profit by either including the current job or skipping it.
from bisect import bisect_right
def jobScheduling(startTime, endTime, profit):
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
end_times = [job[1] for job in jobs]
dp = [0] * (len(jobs) + 1)
for i in range(1, len(jobs) + 1):
k = bisect_right(end_times, jobs[i-1][0])
dp[i] = max(dp[i-1], jobs[i-1][2] + dp[k])
return dp[-1]import java.util.*;
public class JobScheduler {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
int[][] jobs = new int[n][3];
for (int i = 0; i < n; i++) {
jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
}
Arrays.sort(jobs, Comparator.comparingInt(a -> a[1]));
TreeMap<Integer, Integer> dp = new TreeMap<>();
dp.put(0, 0);
for (int[] job : jobs) {
int curProfit = dp.floorEntry(job[0]).getValue() + job[2];
if (curProfit > dp.lastEntry().getValue()) {
dp.put(job[1], curProfit);
}
}
return dp.lastEntry().getValue();
}
}#include <vector>
#include <algorithm>
#include <map>
class Solution {
public:
int jobScheduling(std::vector<int>& startTime, std::vector<int>& endTime, std::vector<int>& profit) {
int n = startTime.size();
std::vector<std::array<int, 3>> jobs(n);
for (int i = 0; i < n; ++i) {
jobs[i] = {startTime[i], endTime[i], profit[i]};
}
std::sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b) {
return a[1] < b[1];
});
std::map<int, int> dp = {{0, 0}};
for (const auto& job : jobs) {
int curProfit = std::prev(dp.upper_bound(job[0]))->second + job[2];
if (curProfit > dp.rbegin()->second) {
dp[job[1]] = curProfit;
}
}
return dp.rbegin()->second;
}
};The solution begins by sorting the jobs in increasing order of their end times. This allows us to consider each job and decide whether to include it based on the results of previously solved subproblems stored in the dp array.
For each job, we perform a binary search using bisect_right to find the index of the last job that doesn't conflict with the current one, and update the maximum profit accordingly.
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the dp array.
Approach 2: Dynamic Programming With Linear Scan
This approach uses dynamic programming to solve the problem by scanning jobs and keeping track of maximum profits without the need of an auxiliary data structure for overlap checking. Instead of binary search, it uses a precomputed array to track the last non-overlapping job for each job.
- Sort the jobs based on their
endTime. - Create a parallel array that holds the index of the last job that doesn’t overlap with the current one.
- Compute the profits including or excluding each job in a linear scan.
def jobScheduling(startTime, endTime, profit):
jobs = list(zip(startTime, endTime, profit))
jobs.sort(key=lambda x: x[1])
n = len(jobs)
dp = [0] * n
dp[0] = jobs[0][2]
for i in range(1, n):
# Include the current job
includeProfit = jobs[i][2]
l = 0
for j in range(i - 1, -1, -1):
if jobs[j][1] <= jobs[i][0]:
includeProfit += dp[j]
break
dp[i] = max(includeProfit, dp[i - 1])
return dp[-1]function jobScheduling(startTime, endTime, profit) {
const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);
jobs.sort((a, b) => a[1] - b[1]);
const dp = Array(jobs.length).fill(0);
dp[0] = jobs[0][2];
for (let i = 1; i < jobs.length; i++) {
let includeProfit = jobs[i][2];
for (let j = i - 1; j >= 0; j--) {
if (jobs[j][1] <= jobs[i][0]) {
includeProfit += dp[j];
break;
}
}
dp[i] = Math.max(dp[i - 1], includeProfit);
}
return dp[dp.length - 1];
}The Python solution sorts jobs by endTime and iterates through each job, computing the maximum profit by considering two cases: including or excluding the current job. It utilizes a nested loop to find the last non-overlapping job in an optimized way, considering constraints on input sizes.
Time Complexity: O(n^2) due to the nested loop search for non-overlapping jobs.
Space Complexity: O(n) for the dp array.
Approach 3: Memoization Search + Binary Search
First, we sort the jobs by start time in ascending order, then design a function dfs(i) to represent the maximum profit that can be obtained starting from the i-th job. The answer is dfs(0).
The calculation process of function dfs(i) is as follows:
For the i-th job, we can choose to do it or not. If we don't do it, the maximum profit is dfs(i + 1); if we do it, we can use binary search to find the first job that starts after the end time of the i-th job, denoted as j, then the maximum profit is profit[i] + dfs(j). We take the larger of the two. That is:
$
dfs(i)=max(dfs(i+1),profit[i]+dfs(j))
Where j is the smallest index that satisfies startTime[j] \ge endTime[i].
In this process, we can use memoization search to save the answer of each state to avoid repeated calculations.
The time complexity is O(n times log n), where n$ is the number of jobs.
function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
const n = startTime.length;
const f = new Array(n).fill(0);
const idx = new Array(n).fill(0).map((_, i) => i);
idx.sort((i, j) => startTime[i] - startTime[j]);
const search = (x: number) => {
let l = 0;
let r = n;
while (l < r) {
const mid = (l + r) >> 1;
if (startTime[idx[mid]] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i] !== 0) {
return f[i];
}
const j = search(endTime[idx[i]]);
return (f[i] = Math.max(dfs(i + 1), dfs(j) + profit[idx[i]]));
};
return dfs(0);
}func jobScheduling(startTime []int, endTime []int, profit []int) int {
n := len(profit)
type tuple struct{ s, e, p int }
jobs := make([]tuple, n)
for i, p := range profit {
jobs[i] = tuple{startTime[i], endTime[i], p}
}
sort.Slice(jobs, func(i, j int) bool { return jobs[i].s < jobs[j].s })
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != 0 {
return f[i]
}
j := sort.Search(n, func(j int) bool { return jobs[j].s >= jobs[i].e })
ans := max(dfs(i+1), jobs[i].p+dfs(j))
f[i] = ans
return ans
}
return dfs(0)
}Approach 4: Dynamic Programming + Binary Search
We can also change the memoization search in Solution 1 to dynamic programming.
First, sort the jobs, this time we sort by end time in ascending order, then define dp[i], which represents the maximum profit that can be obtained from the first i jobs. The answer is dp[n]. Initialize dp[0]=0.
For the i-th job, we can choose to do it or not. If we don't do it, the maximum profit is dp[i]; if we do it, we can use binary search to find the last job that ends before the start time of the i-th job, denoted as j, then the maximum profit is profit[i] + dp[j]. We take the larger of the two. That is:
$
dp[i+1] = max(dp[i], profit[i] + dp[j])
Where j is the largest index that satisfies endTime[j] leq startTime[i].
The time complexity is O(n times log n), where n$ is the number of jobs.
Similar problems:
function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
const n = profit.length;
const jobs: [number, number, number][] = Array.from({ length: n }, (_, i) => [
startTime[i],
endTime[i],
profit[i],
]);
jobs.sort((a, b) => a[1] - b[1]);
const dp: number[] = Array.from({ length: n + 1 }, () => 0);
const search = (x: number, right: number): number => {
let left = 0;
while (left < right) {
const mid = (left + right) >> 1;
if (jobs[mid][1] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
for (let i = 0; i < n; ++i) {
const j = search(jobs[i][0], i);
dp[i + 1] = Math.max(dp[i], dp[j] + jobs[i][2]);
}
return dp[n];
}func jobScheduling(startTime []int, endTime []int, profit []int) int {
n := len(profit)
type tuple struct{ s, e, p int }
jobs := make([]tuple, n)
for i, p := range profit {
jobs[i] = tuple{startTime[i], endTime[i], p}
}
sort.Slice(jobs, func(i, j int) bool { return jobs[i].e < jobs[j].e })
dp := make([]int, n+1)
for i, job := range jobs {
j := sort.Search(i, func(k int) bool { return jobs[k].e > job.s })
dp[i+1] = max(dp[i], dp[j]+job.p)
}
return dp[n]
}class Solution {
func binarySearch<T: Comparable>(inputArr: [T], searchItem: T) -> Int? {
var lowerIndex = 0
var upperIndex = inputArr.count - 1
while lowerIndex < upperIndex {
let currentIndex = (lowerIndex + upperIndex) / 2
if inputArr[currentIndex] <= searchItem {
lowerIndex = currentIndex + 1
} else {
upperIndex = currentIndex
}
}
if inputArr[upperIndex] <= searchItem {
return upperIndex + 1
}
return lowerIndex
}
func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
let zipList = zip(zip(startTime, endTime), profit)
var table: [(startTime: Int, endTime: Int, profit: Int, cumsum: Int)] = []
for ((x, y), z) in zipList {
table.append((x, y, z, 0))
}
table.sort(by: { $0.endTime < $1.endTime })
let sortedEndTime = endTime.sorted()
var profits: [Int] = [0]
for iJob in table {
let index: Int! = binarySearch(inputArr: sortedEndTime, searchItem: iJob.startTime)
if profits.last! < profits[index] + iJob.profit {
profits.append(profits[index] + iJob.profit)
} else {
profits.append(profits.last!)
}
}
return profits.last!
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: |
| Dynamic Programming With Linear Scan | Time Complexity: |
| Memoization Search + Binary Search | – |
| Dynamic Programming + Binary Search | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximum Profit in Job Scheduling easy or hard?
Maximum Profit in Job Scheduling is classified as a Hard problem because it combines interval scheduling with dynamic programming optimization. Recognizing the weighted interval scheduling pattern and integrating binary search for efficient transitions makes it challenging for many candidates.
Maximum Profit in Job Scheduling Python/Java solution
Implementations typically sort the jobs, store start times in a separate array, and use a DP array or memoized recursion. Python solutions often use bisect for binary search, while Java implementations use Arrays.binarySearch or manual binary search logic.
How to solve Maximum Profit in Job Scheduling in O(n log n)?
First combine the inputs into job tuples and sort them by start time. Use dynamic programming where dp[i] stores the maximum profit achievable starting from job i. For each job, perform a binary search to find the next job whose start time is at least the current job's end time, then compute max(skip, take).
What is the best approach for Maximum Profit in Job Scheduling?
Dynamic programming with binary search is the optimal approach. Sort jobs by start time, and for each job compute the best profit between skipping it or taking it and jumping to the next compatible job found via binary search. This reduces the transition lookup to O(log n), producing an overall time complexity of O(n log n).
Is Maximum Profit in Job Scheduling asked at Google/Amazon/Meta?
Maximum Profit in Job Scheduling is a classic weighted interval scheduling problem frequently asked by companies like Google, Amazon, and Meta. It tests dynamic programming, binary search optimization, and reasoning about overlapping intervals.
What data structure is used in Maximum Profit in Job Scheduling?
The solution primarily uses arrays or lists to store sorted job tuples and a dynamic programming array for memoization. Binary search on the sorted start times enables efficient lookup of the next compatible job, making the algorithm O(n log n).
What is the time complexity of Maximum Profit in Job Scheduling?
The optimal solution runs in O(n log n) time. Sorting the jobs takes O(n log n), and each dynamic programming state performs a binary search to locate the next non-overlapping job. Space complexity is O(n) for storing DP results.