Skip to main content

1235. Maximum Profit in Job Scheduling

hardAsked at DRW

DRW asks this problem because it is structurally identical to optimal trade-scheduling with non-overlapping execution windows: given a set of potential trades each with a start time, end time, and expected profit, select a non-overlapping subset that maximizes total profit. Weighted interval scheduling with binary search is the expected approach.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE and quant developer candidates report weighted interval scheduling problems in onsite hard rounds, with explicit connection to trade-schedule optimization.
  • Blind (2025-10)— DRW interview threads note this problem is one of the harder DP+binary-search combinations, valued for its direct mapping to execution scheduling problems.

Problem

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime, and profit arrays. Return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that is scheduled to start at time X.

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

Input
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output
120

Explanation: Jobs [1,3,50] and [3,6,70] do not overlap. Total profit = 120.

Example 2

Input
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output
150

Explanation: Jobs [1,3,20], [4,6,70], [6,9,60] give 150.

Approaches

1. DP + binary search on end times

Sort jobs by end time. dp[i] = max profit using a subset of jobs 0..i. For each job i, use binary search to find the latest job j that ends before job i starts. dp[i] = max(dp[i-1], profit[i] + dp[j]).

Time
O(n log n)
Space
O(n)
function jobScheduling(startTime, endTime, profit) {
  const n = startTime.length;
  // Build and sort jobs by end time
  const jobs = Array.from({ length: n }, (_, i) => [endTime[i], startTime[i], profit[i]]);
  jobs.sort((a, b) => a[0] - b[0]);

  // dp[i] = max profit considering first i jobs
  const dp = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    const [end, start, p] = jobs[i];
    // Binary search: find the latest job that ends <= start of job i
    let lo = 0, hi = i;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (jobs[mid - 1][0] <= start) lo = mid;
      else hi = mid - 1;
    }
    // Option 1: skip job i. Option 2: take job i + best profit up to lo
    dp[i + 1] = Math.max(dp[i], dp[lo] + p);
  }
  return dp[n];
}

Tradeoff: O(n log n) — sort plus binary search per job. O(n) space. This is the canonical DRW answer. State the recurrence before coding: dp[i] = max(skip: dp[i-1], take: profit[i] + dp[last non-overlapping job index]).

DRW-specific tips

Frame the problem in trading terms: 'Each job is a trade execution window. Overlapping windows mean conflicting capital use. I want the maximum-profit non-overlapping trade schedule.' DRW interviewers will then ask: 'What if profits are not fixed but are probability distributions? How do you maximize expected profit under this uncertainty?' This leads into stochastic scheduling — note that the deterministic DP is the starting point and you'd replace profit[i] with E[profit[i]] for risk-neutral optimization. Also: 'What if you have a budget constraint — the sum of chosen job costs ≤ B?' — that is a 2D knapsack extension.

Common mistakes

  • Sorting by start time instead of end time — the DP recurrence requires end-time ordering.
  • Binary search off-by-one: the condition is jobs[mid-1][0] <= start, not < start — jobs ending exactly at start can coexist.
  • Using dp[i-1] incorrectly as the 'skip' case — dp[i+1] = max(dp[i], ...) where dp[i] represents the best using jobs 0..i-1.
  • Not extracting end times into a separate array for the binary search — searching the sorted jobs array directly is cleaner.

Follow-up questions

An interviewer at DRW may pivot to one of these next:

  • What if you want the maximum number of non-overlapping jobs (not maximum profit)? — greedy by earliest end time (Activity Selection).
  • How does the solution change if jobs can overlap but at most 2 can run simultaneously?
  • What is the expected maximum profit if profits are i.i.d. exponential random variables with rate λ?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why sort by end time, not start time?

The DP goes left to right over end times. When considering job i, you need to know which earlier jobs (by end time) are compatible. Sorting by start time would not support efficient binary search for the latest compatible predecessor.

Why is the binary search condition jobs[mid-1][0] <= start?

A job ending exactly at the start time of job i does not overlap — they can coexist. The condition is ≤, not <.

How does this connect to Activity Selection?

Activity Selection maximizes the count of non-overlapping jobs — a greedy by earliest end time achieves O(n log n). Weighted interval scheduling maximizes profit — greedy fails; DP is required.

Practice these live with InterviewChamp.AI

Drill Maximum Profit in Job Scheduling and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →