1235. Maximum Profit in Job Scheduling

Job i runs from startTime[i] to endTime[i] and earns profit[i]. Choose non-overlapping jobs to maximize total profit. A job may start exactly when another ends.

Same recurrence, but since jobs are sorted by end time, binary search for the last job ending at or before the current start.

1function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
2  const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]).sort((a, b) => a[1] - b[1]);
3  const dp = new Array(jobs.length + 1).fill(0);
4  for (let i = 1; i <= jobs.length; i++) {
5    const [s, , p] = jobs[i - 1];
6    let lo = 0, hi = i - 1; // count of jobs ending by s
7    while (lo < hi) { const mid = (lo + hi + 1) >> 1; if (jobs[mid - 1][1] <= s) lo = mid; else hi = mid - 1; }
8    dp[i] = Math.max(dp[i - 1], dp[lo] + p);
9  }
10  return dp[jobs.length];
11}

jobs (by end time)

[1,3]

[2,5]

[4,6]

[6,9]

[3,10]

110

profit

100

dp (best using first i jobs)

Sort jobs by end time.

1 / 0

Space: play/pause · ←/→: step