Dynamic Programming
Maximum Profit in Job Scheduling
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given three arrays, starts, ends, and profits, each representing the start time, end time, and profit of jobs respectively, your task is to schedule the jobs to maximize total profit. You can only work on one job at a time, and once a job has been started, you must finish it before starting another. The goal is to find the maximum profit that can be earned by scheduling jobs such that they do not overlap.
Input:
starts = [1, 3, 6, 10] ends = [4, 5, 10, 12] profits = [20, 20, 100, 70]
The optimal solution would schedule the jobs as follows:
Start the first job at time 1 and complete it by 4 for a profit of 20. Start the next job at time 6 and complete it by 10 for a profit of 100. Start the last job at time 10 and complete it by 12 for a profit of 70.
The total profit is 20 + 100 + 70 = 190
Explanation
Note: The solution below uses the key parameter in the bisect_right function to find the latest job ending before the start time of the current job, which is only available in Python 3.10 and above.
The idea behind this solution is to first sort the jobs by their end times. Afterwards, we initialize an array dp of length len(jobs) + 1 with 0s, where dp[i] represents the maximum profit that can be earned by scheduling the first i jobs (sorted by end time). dp[0] is initialized to 0, as scheduling 0 jobs would yield 0 profit.
Visualization
Python
from bisect import bisect_rightdef job_scheduling(starts, ends, profits):jobs = sorted(zip(starts, ends, profits),key=lambda x: x[1])dp = [0] * (len(jobs) + 1)for i in range(1, len(jobs) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right([job[1] for job in jobs], start)dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
maximum profit in job scheduling
0 / 2
Next, we iterate over each index in dp starting from index 1. At each iteration, we calculate the maximum profit that can be earned by scheduling the first i jobs (sorted by end time). So when i = 1, we are calculating the maximum profit that can be earned by scheduling the first job.
1). We find the corresponding start time and profit of the current job (jobs[i - 1]).
2). Next, we use binary search (bisect_right) to find the number of jobs that have ended before the start time of the current job, and store this number in a variable num_jobs. dp[num_jobs] will also tell us the maximum profit that can be earned by scheduling all the jobs that have ended before the current job.
To breakdown our call to bisect_right: we are looking for the rightmost index in job in job with an end time (key=lambda x: x[1]) that is less than or equal to the start time of the current job (start).
In this case, start = 1, which means this is the first job we can possibly schedule, and num_jobs = 0.
Visualization
Python
from bisect import bisect_rightdef job_scheduling(starts, ends, profits):jobs = sorted(zip(starts, ends, profits),key=lambda x: x[1])dp = [0] * (len(jobs) + 1)for i in range(1, len(jobs) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right([job[1] for job in jobs], start)dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
initialize dp array
0 / 2
Once we have this index, we have two options:
- We can schedule the current job, in which case the profit would be dp[num_jobs] + profit.
- We can skip the current job, in which case the profit would be dp[i - 1].
By taking the maximum of these two options, we can calculate the maximum profit that can be earned by scheduling the first i jobs.
In this case, since this is the first job we can possibly schedule, we schedule it and update dp[i] to dp[num_jobs] + profit.
Visualization
Python
from bisect import bisect_rightdef job_scheduling(starts, ends, profits):jobs = sorted(zip(starts, ends, profits),key=lambda x: x[1])dp = [0] * (len(jobs) + 1)for i in range(1, len(jobs) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right([job[1] for job in jobs], start)dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
num_jobs = 0
0 / 1
Skipping the current job
The next iteration is an example of when we would choose to skip the current job. For this job, start = 3. This job overlaps with the first job, so num_jobs = 0. If we consider the two cases:
- We can schedule the current job, in which case the profit would be dp[num_jobs] + profit = 0 + 18 = 18.
- We can skip the current job, in which case the profit would be dp[i - 1] = 20.
We can see that skipping the current job (in favor of choosing the previous one) would yield a higher profit, so we update dp[i] to dp[i - 1].
Visualization
Python
from bisect import bisect_rightdef job_scheduling(starts, ends, profits):jobs = sorted(zip(starts, ends, profits),key=lambda x: x[1])dp = [0] * (len(jobs) + 1)for i in range(1, len(jobs) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right([job[1] for job in jobs], start)dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
dp[1] = max(0, 0 + 20)
0 / 3
If we examine the state of the dp array at this point, it tells us at that the maximum profit we can obtain from scheduling any combination of the first two jobs is 20.
We can continue this process for the remaining jobs, and the final value of dp[-1] will tell us the maximum profit that can be earned by scheduling all the jobs.
Solution
Visualization
Python
Try these examples:
from bisect import bisect_rightdef job_scheduling(starts, ends, profits):jobs = sorted(zip(starts, ends, profits),key=lambda x: x[1])dp = [0] * (len(jobs) + 1)for i in range(1, len(jobs) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right([job[1] for job in jobs], start)dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
maximum profit in job scheduling
0 / 15
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n * log n) where n is the number of jobs. This is due to the sorting of the jobs, and the binary search for each job.
Space Complexity: O(n) where n is the number of jobs. This is due to the dp array.
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.