Maximum Profit in Job Scheduling
Asked at Airbnb
Problem
Maximum Profit in Job Scheduling gives you jobs with start times, end times, and profits, and asks for the maximum total profit from a set of non-overlapping jobs (a job may start exactly when another ends). It is weighted interval scheduling: sort by end time, then DP with binary search.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Hard | View all Airbnb questions → |
How to Think About It
Greedy by earliest end time works when every job is worth the same, but with profits you must weigh taking a job against skipping it.
Key insight: sort jobs by end time. Let dp[i] be the best profit using only the first i jobs. For job i, either skip it (dp[i-1]) or take it and add its profit to the best result among jobs that end at or before its start.
Because jobs are sorted by end time, "jobs ending at or before start" is a prefix — find its length with binary search (bisect_right(ends, start)).
Transition: dp[i] = max(dp[i-1], dp[j] + profit[i]) where j is that prefix length.
Walkthrough: jobs (1,3,50) (2,4,10) (3,5,40) (3,6,70). Best is 50 (1-3) plus 70 (3-6) = 120.
Optimal Approach
Step 1: Sort jobs by end time; build ends list.
Step 2: dp = [0] * (n + 1).
Step 3: For i from 1 to n with job (s, e, p):
j = bisect_right(ends, s, 0, i - 1) — number of earlier jobs ending at or before s.
dp[i] = max(dp[i-1], dp[j] + p).
Step 4: Return dp[n].
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Sorting by start time and then searching for compatible jobs among later ones — possible, but the end-time ordering makes the prefix DP much cleaner.
Using bisect_left. A job ending exactly at start is compatible, so you need bisect_right.
Linear scan for the previous compatible job, which makes it O(n²).
Greedy by profit or by duration. Neither is optimal; weighted scheduling needs DP.
Solution Code
from bisect import bisect_right
def jobScheduling(startTime, endTime, profit):
jobs = sorted(zip(endTime, startTime, profit))
ends = [e for e, _, _ in jobs]
n = len(jobs)
dp = [0] * (n + 1)
for i in range(1, n + 1):
e, s, p = jobs[i - 1]
j = bisect_right(ends, s, 0, i - 1)
dp[i] = max(dp[i - 1], dp[j] + p)
return dp[n]Frequently Asked Questions
What is the Maximum Profit in Job Scheduling problem?
Maximum Profit in Job Scheduling gives you jobs with start times, end times, and profits, and asks for the maximum total profit from a set of non-overlapping jobs (a job may start exactly when another ends). It is weighted interval scheduling: sort by end time, then DP with binary search.
How do you solve Maximum Profit in Job Scheduling?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Profit in Job Scheduling?
Maximum Profit in Job Scheduling is asked at Airbnb. It is a hard difficulty problem.
What are common mistakes on Maximum Profit in Job Scheduling?
- Sorting by start time and then searching for compatible jobs among later ones — possible, but the end-time ordering makes the prefix DP much cleaner.
- Using `bisect_left`. A job ending exactly at `start` is compatible, so you need `bisect_right`.
- Linear scan for the previous compatible job, which makes it `O(n²)`.
- Greedy by profit or by duration. Neither is optimal; weighted scheduling needs DP.