Maximum Profit in Job Scheduling

Q: Can you also return which jobs were chosen?

Keep the DP array, then walk back from n: if best[i + 1] == best[i], job i was skipped; otherwise it was taken, so record it and jump to its k. This reconstructs one optimal set in O(n).

Q: What if every job paid the same?

Then it is plain interval scheduling, and the greedy "always take the job that ends earliest among those that fit" is optimal in O(n log n) with no DP.

Q: What if you had k workers who could each take non-overlapping jobs?

The single-worker DP no longer works directly. It can be modelled as a min-cost flow on a timeline graph, which handles any k exactly. For small k, a DP over sorted jobs that tracks the end times of each worker is possible but grows quickly.

Pick non-overlapping jobs to maximize total profit. Weighted interval scheduling: sort by end time, then combine dynamic programming with binary search. Solve it below in Python or JavaScript, then read the walkthrough.

Solve it in your browser Read the solution

HardArray Binary Search Dynamic Programming Sorting Asked at 99 companies incl. Google, Amazon, Meta

Problem

You have n jobs. Job i starts at startTime[i], ends at endTime[i], and pays profit[i].

Choose a set of jobs so that no two of them overlap in time, and return the largest total profit you can earn.

A job that ends at time t does not overlap a job that starts at time t, so you can finish one and start the next at the same moment.

Example 1

Input: startTime = [1, 2, 4, 6], endTime = [4, 5, 7, 9], profit = [20, 30, 15, 25]
Output: 55

Take job 1 (2 to 5, pays 30) and job 3 (6 to 9, pays 25). Job 0 plus job 3 gives only 45.

Example 2

Input: startTime = [0, 3, 6], endTime = [3, 6, 9], profit = [5, 5, 5]
Output: 15

Each job starts exactly when the previous one ends, so all three fit.

Example 3

Input: startTime = [1, 1, 1], endTime = [10, 3, 5], profit = [40, 10, 25]
Output: 40

All three start at time 1, so only one can be chosen.

Constraints

1 ≤ n ≤ 5 · 10⁴
startTime.length == endTime.length == profit.length == n
0 ≤ startTime[i] < endTime[i] ≤ 10⁹
1 ≤ profit[i] ≤ 10⁴

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Maximum Profit in Job Scheduling in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Maximum Profit in Job Scheduling

Pattern: Sort by end + DP + binary search

Greedy rules like "earliest end first" or "highest profit first" break as soon as profits differ, so think in terms of choices: for each job, either skip it or take it.

Sort jobs by end time. Let best[i] be the most profit using only the first i jobs. For job i:

Skip it: best[i].
Take it: its profit plus the best you can do with jobs that end at or before its start. Because jobs are sorted by end time, those jobs form a prefix, and binary search finds where it ends.

So best[i + 1] = max(best[i], profit + best[k]), where k is the number of jobs whose end is at most this job's start.

Approach 1: Try every subset

Enumerate all 2ⁿ subsets, keep the ones with no overlaps, and take the best profit. Only usable for tiny inputs.

Time O(2ⁿ · n) · Space O(n)

Approach 2: DP with a linear scan for the previous job

Same recurrence, but find the last compatible job by scanning backwards from i. Correct, and fine for a few thousand jobs, but quadratic when many jobs overlap.

Time O(n²) · Space O(n)

Approach 3: DP with binary search

Zip the jobs together and sort by end time. Keep an array of end times.
best[0] = 0. For job i (0-based) with start s, find k = bisect_right(ends, s), the count of jobs ending at or before s.
best[i + 1] = max(best[i], best[k] + profit_i).
Return best[n].

Using bisect_right on s is what makes a job ending exactly at s count as compatible.

Time O(n log n) · Space O(n)

Approach	Time	Space
Try every subset	O(2ⁿ · n)	O(n)
DP with a linear scan for the previous job	O(n²)	O(n)
DP with binary search	O(n log n)	O(n)

Solution code

Try the practice editor first. Both solutions pass every test above.

Maximum Profit in Job Scheduling solution in Python

from bisect import bisect_right


def job_scheduling(start_time: list[int], end_time: list[int], profit: list[int]) -> int:
    jobs = sorted(zip(end_time, start_time, profit))
    ends = [e for e, _, _ in jobs]
    best = [0] * (len(jobs) + 1)
    for i, (_, s, p) in enumerate(jobs):
        k = bisect_right(ends, s)  # jobs that end at or before s
        best[i + 1] = max(best[i], best[k] + p)
    return best[-1]

Maximum Profit in Job Scheduling solution in JavaScript

function jobScheduling(startTime, endTime, profit) {
  const jobs = startTime.map((s, i) => [endTime[i], s, profit[i]]);
  jobs.sort((a, b) => a[0] - b[0]);
  const best = new Array(jobs.length + 1).fill(0);

  // Number of jobs whose end time is <= t.
  const countEndingBy = (t) => {
    let lo = 0;
    let hi = jobs.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (jobs[mid][0] <= t) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };

  jobs.forEach(([, s, p], i) => {
    best[i + 1] = Math.max(best[i], best[countEndingBy(s)] + p);
  });
  return best[jobs.length];
}

Common mistakes

Using a greedy choice (earliest end, highest profit, best profit per hour). Each one has counterexamples.
Treating touching jobs as overlapping. A job ending at t is compatible with one starting at t, so search with "≤ start", not "< start".
Sorting only one of the three arrays, which breaks the link between a job's times and its profit.
Off-by-one between "index of the last compatible job" and "number of compatible jobs" when indexing the DP array.

What interviewers look for

Open by showing why greedy fails with a two-line counterexample, then state the take-or-skip recurrence. Interviewers are mainly checking that you recognise weighted interval scheduling and can justify sorting by end time: it makes the compatible jobs a prefix, which is what allows binary search.

Be precise about the boundary case where one job ends exactly when another starts, and say which binary search variant you use and why.

Follow-up questions

Can you also return which jobs were chosen?

Keep the DP array, then walk back from n: if best[i + 1] == best[i], job i was skipped; otherwise it was taken, so record it and jump to its k. This reconstructs one optimal set in O(n).

What if every job paid the same?

Then it is plain interval scheduling, and the greedy "always take the job that ends earliest among those that fit" is optimal in O(n log n) with no DP.

What if you had k workers who could each take non-overlapping jobs?

The single-worker DP no longer works directly. It can be modelled as a min-cost flow on a timeline graph, which handles any k exactly. For small k, a DP over sorted jobs that tracks the end times of each worker is possible but grows quickly.

Companies that ask Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling is tagged by 99 companies in our interview dataset. The score shows how often it comes up at each company.

and 75 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Maximum Profit in Job Scheduling

Solve it in your browser Read the solution

HardArray Binary Search Dynamic Programming Sorting Asked at 99 companies incl. Google, Amazon, Meta

Problem

You have n jobs. Job i starts at startTime[i], ends at endTime[i], and pays profit[i].

Choose a set of jobs so that no two of them overlap in time, and return the largest total profit you can earn.

A job that ends at time t does not overlap a job that starts at time t, so you can finish one and start the next at the same moment.

Example 1

Input: startTime = [1, 2, 4, 6], endTime = [4, 5, 7, 9], profit = [20, 30, 15, 25]
Output: 55

Take job 1 (2 to 5, pays 30) and job 3 (6 to 9, pays 25). Job 0 plus job 3 gives only 45.

Example 2

Input: startTime = [0, 3, 6], endTime = [3, 6, 9], profit = [5, 5, 5]
Output: 15

Each job starts exactly when the previous one ends, so all three fit.

Example 3

Input: startTime = [1, 1, 1], endTime = [10, 3, 5], profit = [40, 10, 25]
Output: 40

All three start at time 1, so only one can be chosen.

Constraints

1 ≤ n ≤ 5 · 10⁴
startTime.length == endTime.length == profit.length == n
0 ≤ startTime[i] < endTime[i] ≤ 10⁹
1 ≤ profit[i] ≤ 10⁴

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Maximum Profit in Job Scheduling in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Maximum Profit in Job Scheduling

Pattern: Sort by end + DP + binary search

Greedy rules like "earliest end first" or "highest profit first" break as soon as profits differ, so think in terms of choices: for each job, either skip it or take it.

Sort jobs by end time. Let best[i] be the most profit using only the first i jobs. For job i:

Skip it: best[i].
Take it: its profit plus the best you can do with jobs that end at or before its start. Because jobs are sorted by end time, those jobs form a prefix, and binary search finds where it ends.

So best[i + 1] = max(best[i], profit + best[k]), where k is the number of jobs whose end is at most this job's start.

Approach 1: Try every subset

Enumerate all 2ⁿ subsets, keep the ones with no overlaps, and take the best profit. Only usable for tiny inputs.

Time O(2ⁿ · n) · Space O(n)

Approach 2: DP with a linear scan for the previous job

Same recurrence, but find the last compatible job by scanning backwards from i. Correct, and fine for a few thousand jobs, but quadratic when many jobs overlap.

Time O(n²) · Space O(n)

Approach 3: DP with binary search

Zip the jobs together and sort by end time. Keep an array of end times.
best[0] = 0. For job i (0-based) with start s, find k = bisect_right(ends, s), the count of jobs ending at or before s.
best[i + 1] = max(best[i], best[k] + profit_i).
Return best[n].

Using bisect_right on s is what makes a job ending exactly at s count as compatible.

Time O(n log n) · Space O(n)

Approach	Time	Space
Try every subset	O(2ⁿ · n)	O(n)
DP with a linear scan for the previous job	O(n²)	O(n)
DP with binary search	O(n log n)	O(n)

Solution code

Try the practice editor first. Both solutions pass every test above.

Maximum Profit in Job Scheduling solution in Python

from bisect import bisect_right


def job_scheduling(start_time: list[int], end_time: list[int], profit: list[int]) -> int:
    jobs = sorted(zip(end_time, start_time, profit))
    ends = [e for e, _, _ in jobs]
    best = [0] * (len(jobs) + 1)
    for i, (_, s, p) in enumerate(jobs):
        k = bisect_right(ends, s)  # jobs that end at or before s
        best[i + 1] = max(best[i], best[k] + p)
    return best[-1]

Maximum Profit in Job Scheduling solution in JavaScript

function jobScheduling(startTime, endTime, profit) {
  const jobs = startTime.map((s, i) => [endTime[i], s, profit[i]]);
  jobs.sort((a, b) => a[0] - b[0]);
  const best = new Array(jobs.length + 1).fill(0);

  // Number of jobs whose end time is <= t.
  const countEndingBy = (t) => {
    let lo = 0;
    let hi = jobs.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (jobs[mid][0] <= t) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };

  jobs.forEach(([, s, p], i) => {
    best[i + 1] = Math.max(best[i], best[countEndingBy(s)] + p);
  });
  return best[jobs.length];
}

Common mistakes

Using a greedy choice (earliest end, highest profit, best profit per hour). Each one has counterexamples.
Treating touching jobs as overlapping. A job ending at t is compatible with one starting at t, so search with "≤ start", not "< start".
Sorting only one of the three arrays, which breaks the link between a job's times and its profit.
Off-by-one between "index of the last compatible job" and "number of compatible jobs" when indexing the DP array.

What interviewers look for

Be precise about the boundary case where one job ends exactly when another starts, and say which binary search variant you use and why.

Follow-up questions

Can you also return which jobs were chosen?

Keep the DP array, then walk back from n: if best[i + 1] == best[i], job i was skipped; otherwise it was taken, so record it and jump to its k. This reconstructs one optimal set in O(n).

What if every job paid the same?

Then it is plain interval scheduling, and the greedy "always take the job that ends earliest among those that fit" is optimal in O(n log n) with no DP.

What if you had k workers who could each take non-overlapping jobs?

Companies that ask Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling is tagged by 99 companies in our interview dataset. The score shows how often it comes up at each company.

and 75 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Maximum Profit in Job Scheduling

Approach 1: Try every subset

Approach 2: DP with a linear scan for the previous job

Approach 3: DP with binary search

Solution code

Common mistakes

What interviewers look for

Follow-up questions

Can you also return which jobs were chosen?

What if every job paid the same?

What if you had k workers who could each take non-overlapping jobs?

Companies that ask Maximum Profit in Job Scheduling

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Maximum Profit in Job Scheduling

Approach 1: Try every subset

Approach 2: DP with a linear scan for the previous job

Approach 3: DP with binary search

Solution code

Common mistakes

What interviewers look for

Follow-up questions

Can you also return which jobs were chosen?

What if every job paid the same?

What if you had k workers who could each take non-overlapping jobs?

Companies that ask Maximum Profit in Job Scheduling

Practice next

Get live help in the real interview