Maximum Profit in Job Scheduling

hard dp binary search

Problem

Each job has a start time, end time, and profit. Select a subset of non-overlapping jobs maximizing the total profit. (Jobs ending at time t do not overlap with jobs starting at time t.)

Inputstart=[1,2,3,3], end=[3,4,5,6], profit=[50,10,40,70]

Output120

Take jobs (1→3, 50) and (3→6, 70) for profit 120.

start

end

profit

from bisect import bisect_right

def job_scheduling(start, end, profit):
    jobs = sorted(zip(end, start, profit))
    ends = [j[0] for j in jobs]
    n = len(jobs)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        e, s, p = jobs[i - 1]
        j = bisect_right(ends, s, 0, i - 1)
        dp[i] = max(dp[i - 1], p + dp[j])
    return dp[n]

function jobScheduling(start, end, profit) {
  const n = start.length;
  const jobs = Array.from({ length: n }, (_, i) => [end[i], start[i], profit[i]]);
  jobs.sort((a, b) => a[0] - b[0]);
  const ends = jobs.map(j => j[0]);
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    const [e, s, p] = jobs[i - 1];
    let lo = 0, hi = i - 1;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (ends[m] <= s) lo = m + 1; else hi = m;
    }
    dp[i] = Math.max(dp[i - 1], p + dp[lo]);
  }
  return dp[n];
}

class Solution {
    public int jobScheduling(int[] start, int[] end, int[] profit) {
        int n = start.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{ end[i], start[i], profit[i] };
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int s = jobs[i - 1][1], p = jobs[i - 1][2];
            int lo = 0, hi = i - 1;
            while (lo < hi) {
                int m = (lo + hi) >>> 1;
                if (jobs[m][0] <= s) lo = m + 1; else hi = m;
            }
            dp[i] = Math.max(dp[i - 1], p + dp[lo]);
        }
        return dp[n];
    }
}

int jobScheduling(vector<int>& start, vector<int>& end, vector<int>& profit) {
    int n = start.size();
    vector<array<int, 3>> jobs(n);
    for (int i = 0; i < n; i++) jobs[i] = { end[i], start[i], profit[i] };
    sort(jobs.begin(), jobs.end());
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int s = jobs[i - 1][1], p = jobs[i - 1][2];
        int lo = 0, hi = i - 1;
        while (lo < hi) {
            int m = (lo + hi) / 2;
            if (jobs[m][0] <= s) lo = m + 1; else hi = m;
        }
        dp[i] = max(dp[i - 1], p + dp[lo]);
    }
    return dp[n];
}

Explanation

For each job you face one decision: skip it or take it. The clever move is to first sort all jobs by their end time, so that once you decide to take a job, you only need to look "back in time" to find earlier jobs that finish before it starts.

We build dp where dp[i] is the best profit using the first i jobs (in sorted order). For job i we compare two options: ignore it (dp[i-1]) or take its profit p plus the best profit from jobs that end at or before this job's start time.

To find that earlier set fast, we use binary search (bisect_right on the sorted end times) to locate the last job that doesn't overlap. That gives us dp[j] in O(log n) instead of scanning everything.

Example: jobs sorted by end are [1→3 $50], [2→4 $10], [3→5 $40], [3→6 $70]. Taking the first ($50) and the last (starts at 3, so it can sit after the first, $70) gives 120, which beats every other combination.

Because the jobs are sorted once and each lookup is a quick binary search, the whole thing runs in O(n log n).

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