Maximum Profit in Job Scheduling

There are n jobs. Job i starts at time startTime[i], finishes at time endTime[i], and earns profit[i] if you take it.

You can work on only one job at a time, so the jobs you choose must not overlap. A job that finishes at time x may be followed by a job that starts at exactly time x.

Return the largest total profit you can earn from a set of non-overlapping jobs. The jobs are given in no particular order.

Example 1

Example 2

Example 3

Constraints

• 1 <= n == startTime.length == endTime.length == profit.length <= 5 · 10⁴
• 1 <= startTime[i] < endTime[i] <= 109
• 1 <= profit[i] <= 104

Pattern Path · Dynamic Programming · problem 159 of 169

Start simple

Try every subset of jobs and keep the most profitable one with no overlaps: O(2ⁿ · n) time; a DP that scans backwards for the last compatible job is O(n²).

The key idea

Sort the jobs by end time. Let best[i] be the maximum profit using only the first i jobs in that order. For job i there are two choices:

• Skip it: the answer stays best[i].
• Take it: earn its profit, plus the best you could do with jobs that end no later than it starts. Because the jobs are sorted by end time, those jobs form a prefix, the first j jobs, so the value is best[j] + profit.

So best[i+1] = max(best[i], best[j] + profit). Find j by binary search on the sorted end times: it is the number of end times <= start, which is exactly what bisect_right returns.

Why sorting by end works: every job compatible with job i that comes earlier finishes by its start, and these form a contiguous prefix of the sorted list, so one DP value summarises all of them. A greedy choice (highest profit first, or earliest end first) fails because profits differ; the DP weighs both options for every job.

Complexity

• Time: O(n log n)
• Space: O(n)

Python

from bisect import bisect_right


class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))
        ends = [end for end, _, _ in jobs]
        # best[i] = max profit using only the first i jobs (sorted by end time)
        best = [0] * (len(jobs) + 1)
        for i, (end, start, gain) in enumerate(jobs):
            # Jobs 0..j-1 all finish by the time this one starts.
            j = bisect_right(ends, start, 0, i)
            best[i + 1] = max(best[i], best[j] + gain)
        return best[-1]

JavaScript

var jobScheduling = function(startTime, endTime, profit) {
  const jobs = startTime.map((start, i) => [start, endTime[i], profit[i]]);
  jobs.sort((a, b) => a[1] - b[1]);

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

  // best[i] = max profit using only the first i jobs (sorted by end time)
  const best = new Array(jobs.length + 1).fill(0);
  for (let i = 0; i < jobs.length; i++) {
    const [start, , gain] = jobs[i];
    const j = countEndingBy(start, i);
    best[i + 1] = Math.max(best[i], best[j] + gain);
  }
  return best[jobs.length];
};

What the interviewer is checking

This is weighted interval scheduling. The interviewer wants to see you reject greedy with a counterexample, set up a take-or-skip DP over sorted jobs, and speed up the transition with binary search.

Mistakes to avoid

• Treating a job that starts exactly when another ends as overlapping (use <= when comparing end to start).
• Sorting by start time but looking up compatible jobs by end time, or losing the pairing of start, end and profit when sorting.
• Using a greedy rule, which picks the wrong jobs when one long job pays more or less than several short ones.
• Scanning backwards linearly for the previous compatible job, which is O(n²) on large inputs.

Follow-ups to expect

• Return the chosen jobs, not just the profit. (Backtrack through the DP table.)
• What if you can run up to k jobs at once? (Harder: min-cost flow formulation.)
• What if all profits are equal? (Greedy by end time suffices.)

In real software

Ad schedulers, freelance gig planners and cloud spot-instance bidders all choose a non-overlapping set of time slots that maximises total value.

Practice next