hard

Maximum Profit in Job Scheduling

Pick non-overlapping jobs that maximize total profit.

1. Define the problem

Maximum Profit in Job Scheduling

You are given n jobs, each with a startTime, endTime, and profit. You are also given the arrays startTime, endTime, and profit, where the ith job has startTimei, endTimei, and profiti. You are given some queries as jobs, but really there is just one rule: you can only work on one job at a time , meaning any two jobs you pick cannot overlap even at their boundary (a job that ends when another starts is fine to chain, since they don't overlap). Return the maximum profit you can take on. Sort jobs by end time. Then for each job, in order, decide whether including it beats skipping it — including it means adding its profit to the best result achievable from jobs that finished by the time this one starts, which you find with a binary search over already-sorted end times . This is dynamic programming layered on top of sorting and searching.

Constraints

  • 1 ≤ startTime.length == endTime.length == profit.length ≤ 5 × 104
  • 1 ≤ startTimei < endTimei ≤ 109
  • 1 ≤ profiti ≤ 104

Example

InputstartTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70]
Output120

Explanation The subset of jobs selected is the first and fourth job, [1, 3] and [3, 6], with a profit of 50 + 70 = 120.

2. Know the words first

In plain terms

Non-overlapping
Two jobs don't overlap if one ends at or before the other begins — like two back-to-back meetings with no shared time in between.
3. Visualize the solution

Sort by end time, then decide include-or-skip with a binary search

Sort by end time, then decide include-or-skip with a binary search
Statusinit

Sorted by end time: [1,3,50], [2,4,10], [3,5,40], [3,6,70]. Job 0 (start1,end3,profit50): no earlier jobs end by start=1, so p=0. dp[1] = max(dp[0]=0, dp[0]+50=50) = 50.

What happens in this step

job 0: start=1, end=3, profit=50
jobs ending <= 1 among earlier jobs: none -> p = 0
dp[1] = max(dp[0] = 0, dp[0] + 50 = 50) = 50
Step 1 of 4

Steps to visualize

  1. Sort jobs by endTime, and build a dp array where dpi is the best profit using the first i sorted jobs.
  2. For each job in sorted order, binary search among the earlier jobs' end times for the count that finish at or before this job's start.
  3. That search result points at the best dp value compatible with also taking this job — add this job's profit to it.
  4. dp advances to the better of "skip this job" (carry forward the previous dp value) and "take this job".
  5. The final dp entry holds the maximum achievable profit.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sort by end time, then decide include-or-skip with a binary search
Statusinit

Sorted by end time: [1,3,50], [2,4,10], [3,5,40], [3,6,70]. Job 0 (start1,end3,profit50): no earlier jobs end by start=1, so p=0. dp[1] = max(dp[0]=0, dp[0]+50=50) = 50.

What happens in this step

job 0: start=1, end=3, profit=50
jobs ending <= 1 among earlier jobs: none -> p = 0
dp[1] = max(dp[0] = 0, dp[0] + 50 = 50) = 50
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function jobScheduling(startTime, endTime, profit) {
  const n = startTime.length;
  const jobs = Array.from({ length: n }, (_, i) => [startTime[i], endTime[i], profit[i]]);
  jobs.sort((a, b) => a[1] - b[1]);

  const ends = jobs.map((job) => job[1]);
  const dp = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    const [start, , jobProfit] = jobs[i];
    let lo = 0;
    let hi = i;

    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (ends[mid - 1] <= start) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }

    const takeProfit = dp[lo] + jobProfit;
    dp[i + 1] = Math.max(dp[i], takeProfit);
  }

  return dp[n];
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70]120example from the docstring
startTime = [1], endTime = [2], profit = [5]5smallest valid input: a single job
startTime = [1, 1, 1], endTime = [5, 5, 5], profit = [10, 20, 30]30every job overlaps every other, so only the single best-paying job can be taken
startTime = [1, 2, 3, 4], endTime = [2, 3, 4, 5], profit = [5, 6, 4, 5]20every job is back-to-back with no overlap, so all can be taken
startTime = [1, 3], endTime = [3, 6], profit = [10, 10]20a job that starts exactly when another ends is not an overlap
startTime = [1, 1, 1], endTime = [4, 2, 3], profit = [3, 1, 1]3taking two smaller non-overlapping jobs still cannot beat the single big blocking job

Keep reading