Topics › Dynamic Programming › 1D DP

Maximum Profit in Job Scheduling

Medium TUF ID 691 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

There are n jobs. Job i runs from startTime[i] to endTime[i] and earns profit[i]. Choose a set of jobs with no two overlapping in time, and maximise the total profit. A job that ends at time X does not overlap a job that starts at time X: you can finish one and start the next at the same instant.

Constraints (LeetCode 1235): 1 ≤ n ≤ 5 × 10^4, 1 ≤ startTime[i] < endTime[i] ≤ 10^9, 1 ≤ profit[i] ≤ 10^4. The total profit is at most 5 × 10^8, which fits in an int.

Example 1

start  = [1, 2, 3, 3]
end    = [3, 4, 5, 6]
profit = [50, 10, 40, 70]
answer = 120        // job [1,3) for 50, then job [3,6) for 70

Example 2

start  = [1, 2, 3, 4, 6]
end    = [3, 5, 10, 6, 9]
profit = [20, 20, 100, 70, 60]
answer = 150        // [1,3) + [4,6) + [6,9) = 20 + 70 + 60

Why greedy is not enough

The classic “pick the job that ends first” greedy (the activity selection rule from N meetings in one room) maximises the number of jobs, not the profit. With weights it fails immediately: jobs [1, 10) worth 100 and [2, 3), [4, 5) worth 30 each. Earliest-ending picks the two short jobs (60), but the single long job is worth 100. Picking the most profitable job first fails the other way: one job worth 50 can block three compatible jobs worth 40 each. We need to weigh “take this job” against “skip it” with full knowledge of what each choice leaves available.

The recurrence: take or skip, in start-time order

Sort the jobs by start time. Now consider them in that order and let best(i) be the maximum profit using only jobs i, i + 1, ..., n - 1. For job i there are two choices:

• Skip it: the answer is best(i + 1).
• Take it: earn profit[i], and the next job we may take is the first one whose start is ≥ end[i]. Call that index next(i). The answer is profit[i] + best(next(i)).

Why is it safe to jump straight to next(i)? Jobs between i + 1 and next(i) - 1 start before job i ends (and at or after it starts), so they overlap job i and cannot be taken. Every job from next(i) onward starts after job i ends, and since we only look forward, none of them can conflict with anything chosen before i. So the remaining problem is exactly best(next(i)).

best(n) = 0
best(i) = max( best(i + 1),  profit[i] + best(next(i)) )
answer  = best(0)

Sorting by start time is what makes next(i) a suffix boundary: everything compatible with job i is a contiguous block at the end of the array, so it can be found by binary search.

Approach 1: Recursion

Intuition. Code the recurrence with a linear scan for next(i).

Algorithm.

1. Build {start, end, profit} triples and sort them by start.
2. best(i): if i == n return 0; scan forward from i + 1 to find next; return the larger of skip and take.

static int[][] sortedByStart(int[] start, int[] end, int[] profit) {
    int n = start.length;
    int[][] jobs = new int[n][];
    for (int i = 0; i < n; i++) jobs[i] = new int[]{start[i], end[i], profit[i]};
    Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
    return jobs;
}

static int recursion(int[] start, int[] end, int[] profit) {
    return best(0, sortedByStart(start, end, profit));
}

static int best(int i, int[][] jobs) {
    if (i == jobs.length) return 0;
    int skip = best(i + 1, jobs);
    int next = i + 1;
    while (next < jobs.length && jobs[next][0] < jobs[i][1]) next++;   // first job starting once job i has ended
    int take = jobs[i][2] + best(next, jobs);
    return Math.max(skip, take);
}

Complexity. Time O(2^n) in the worst case (when no jobs overlap, both branches stay alive at every level). Space O(n) for the stack.

Approach 2: Memoization with binary search

Intuition. best(i) depends only on i, so there are n states; cache them. The remaining cost is finding next(i). Because the jobs are sorted by start time, “first job with start ≥ end[i]” is a lower bound query, answered in O(log n) by binary search.

Algorithm.

1. Sort as before.
2. memo(i): return the cached value if present; otherwise compute max(memo(i + 1), profit[i] + memo(lowerBound(end[i]))) and cache it.

static int firstStartingAtOrAfter(int[][] jobs, int time) {
    int lo = 0, hi = jobs.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (jobs[mid][0] >= time) hi = mid; else lo = mid + 1;
    }
    return lo;
}

static int memoization(int[] start, int[] end, int[] profit) {
    int[][] jobs = sortedByStart(start, end, profit);
    int[] dp = new int[jobs.length];
    Arrays.fill(dp, -1);
    return memo(0, jobs, dp);
}

static int memo(int i, int[][] jobs, int[] dp) {
    if (i == jobs.length) return 0;
    if (dp[i] != -1) return dp[i];
    int skip = memo(i + 1, jobs, dp);
    int take = jobs[i][2] + memo(firstStartingAtOrAfter(jobs, jobs[i][1]), jobs, dp);
    return dp[i] = Math.max(skip, take);
}

Complexity. Time O(n log n): the sort, plus n states each with one binary search. Space O(n) for the cache and up to O(n) stack.

That stack is a real problem: the “skip” chain memo(0) → memo(1) → ... → memo(n) is n frames deep, and n = 5 × 10^4 can overflow Java’s default thread stack. The bottom-up version avoids it.

Approach 3: Tabulation

Intuition. best(i) reads only best(i + 1) and best(next(i)), both with larger indices. So fill dp from n - 1 down to 0, and the values we need are always ready. Same recurrence, same complexity, no recursion.

Algorithm.

1. Sort the jobs by start time; dp[n] = 0.
2. For i from n - 1 down to 0: next = lowerBound(end[i]), dp[i] = max(dp[i + 1], profit[i] + dp[next]).
3. Return dp[0].

static int tabulation(int[] start, int[] end, int[] profit) {
    int[][] jobs = sortedByStart(start, end, profit);
    int n = jobs.length;
    int[] dp = new int[n + 1];                         // dp[i]: best profit using only jobs[i..n-1]; dp[n] = 0
    for (int i = n - 1; i >= 0; i--) {
        int next = firstStartingAtOrAfter(jobs, jobs[i][1]);
        dp[i] = Math.max(dp[i + 1], jobs[i][2] + dp[next]);
    }
    return dp[0];
}

Dry run on Example 1. After sorting by start: A = [1,3) 50, B = [2,4) 10, C = [3,5) 40, D = [3,6) 70 (indices 0 to 3).

Complexity. Time O(n log n). Space O(n) for the jobs array and dp.

An equivalent formulation sorts by end time and asks, for each job, “what is the best profit among jobs ending at or before my start?” using a TreeMap from end time to best profit. It has the same complexity; the start-sorted version above has the advantage of reusing the same take/skip pattern as knapsack and house robber.

Edge cases and pitfalls

• Touching jobs. end[i] == start[j] is allowed. The binary search must find the first start ≥ end[i], not > end[i]. The test [3,5) with [1,3) checks this.
• Unsorted input. The input arrays are not sorted. Sort triples, never the three arrays separately, or the start, end and profit of a job get separated.
• Recursion depth. Prefer the tabulated version for n in the tens of thousands.
• Equal start times. Several jobs may start together. The lower-bound search returns the first of them, so none is skipped by accident.
• Overflow. Within LeetCode’s limits int suffices. If profits can be up to 10^9, use long for dp.
• Comparator overflow. Use Integer.compare rather than a[0] - b[0]. Subtraction happens to be safe for these positive times, but it overflows as soon as values can be large and of mixed sign.

Related problems

• N meetings in one room is the unweighted version, where the earliest-end greedy is optimal.
• Non-overlapping Intervals asks for the fewest removals to make intervals disjoint.
• Job sequencing Problem has unit-time jobs with deadlines and a greedy solution.
• House robber has the same take/skip recurrence where “next compatible” is always i + 2.
• Lower Bound explains the binary search used to find next(i).