Back to Main
Learn DSA
Depth-First Search
Greedy Algorithms
Get Premium
Dynamic Programming
Maximum Profit in Job Scheduling
medium
DESCRIPTION (credit 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:
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 5 and complete it by 10 for a profit of 100.
The total profit is 20 + 100 = 120
Explanation
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.
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(dp) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right(jobs, start, key=lambda x: x[1])dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
maximum profit in job scheduling
0 / 2
1x
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.
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(dp) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right(jobs, start, key=lambda x: x[1])dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
initialize dp array
0 / 2
1x
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.
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(dp) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right(jobs, start, key=lambda x: x[1])dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
num_jobs = 0
0 / 1
1x
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].
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(dp) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right(jobs, start, key=lambda x: x[1])dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
dp[1] = max(0, 0 + 20)
0 / 3
1x
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
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(dp) + 1):start, end, profit = jobs[i - 1]# find number of jobs to finish before start of current jobnum_jobs = bisect_right(jobs, start, key=lambda x: x[1])dp[i] = max(dp[i - 1], dp[num_jobs] + profit)return dp[-1]
maximum profit in job scheduling
0 / 15
1x
Complexity Analysis
- Time complexity: O(n * log n) due to the sorting of the jobs, and the binary search for each job.
- Space complexity: O(n) due to the dp array.
Login to track your progress
Your account is free and you can post anonymously if you choose.