HardArrayBinary SearchDynamic ProgrammingSortingUpdated Sep 2026

1235. Maximum Profit in Job Scheduling

Asked at Airbnb

Difficulty

Hard

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given n jobs. Job i runs from startTime[i] to endTime[i] and pays profit[i]. You want to pick a subset of jobs that earns the most money.

The rule: no two chosen jobs may overlap in time. A job that ends at time X and a job that starts at time X are not overlapping, so you may take both. In other words, each chosen job must start at or after the end time of the previous chosen job.

Return the maximum total profit you can collect from such a non-overlapping subset. You do not need to report which jobs you picked, only the total.

Pick jobs that do not overlap

jobsstartendprofit12341350241035403670Rows 1 and 4 are compatible: 1-3 then 3-6, totalprofit 50 + 70 = 120.
Job 1 (1-3) and job 4 (3-6) touch at time 3, so both can be taken for a total of 120.

Constraints

  • ●1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
  • ●1 <= startTime[i] < endTime[i] <= 10^9
  • ●1 <= profit[i] <= 10^4

Examples

Example 1
InputstartTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output120
WhyTake job 1 (1 to 3, profit 50) and job 4 (3 to 6, profit 70). Job 4 starts exactly when job 1 ends, so they do not overlap. Total = 50 + 70 = 120, which beats every other combination.
Example 2
InputstartTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output150
WhyTake job 1 (1 to 3, profit 20), job 4 (4 to 6, profit 70) and job 5 (6 to 9, profit 60). They touch but never overlap. Total = 20 + 70 + 60 = 150. Taking the big job 3 (profit 100) blocks too much time, so it loses.
Example 3
InputstartTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output6
WhyAll three jobs start at time 1, so they all overlap each other. You can only take one, and the middle job pays the most: 6.

Asked At

1 companies
CompanyDifficulty
AirbnbHardView all Airbnb questions →

How to Think About It

1

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.

2

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.

3

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)).

4

Transition: dp[i] = max(dp[i-1], dp[j] + profit[i]) where j is that prefix length.

5

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).

Sort by end time, then DP with binary search

sorted by endstartendprofit12341350241035403670Jobs are ordered by end time, so compatible earlierjobs always form a prefix.dp050509012001234dp[i] is the best profit using the first i jobs.dp[1]=50, dp[2]=50, dp[3]=90, dp[4]=120.sort jobs by end timebinary search: last job ending <= startdp[i] = max(dp[i-1], dp[j] + profit[i])answer = dp[n]Each job is decided once, and the binary search findsthe best compatible prefix in O(log n).
For each job we choose the better of skipping it or taking it plus the best earlier compatible job.
ComplexityTime O(n log n)Space O(n)The sort and the binary search inside the loop each cost O(log n) per job, and the dp array plus the ends list need O(n) memory.

What Trips People Up in Real Interviews

1

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.

2

Using bisect_left. A job ending exactly at start is compatible, so you need bisect_right.

3

Linear scan for the previous compatible job, which makes it O(n²).

4

Greedy by profit or by duration. Neither is optimal; weighted scheduling needs DP.

Solution Code

O(n log n) time
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]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.