Maximum Profit in Job Scheduling

How it works

We can convert the top-down approach to bottom-up by iterating from the last job to the first. At each position, we compute the maximum profit considering all jobs from that point onwards. This eliminates recursion overhead.

Steps

1. Sort indices by start time.
2. Create a DP array where dp[i] represents the maximum profit starting from job i.
3. Iterate from n-1 down to 0.
4. For each job, use binary search to find the next non-overlapping job.
5. dp[i] = max(dp[i+1], profit[i] + dp[j]) where j is the next non-overlapping job.
6. Return dp[0].

Complexity

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

Things to watch for

Sorting by End Time Instead of Start Time

For the top-down DP approach, jobs must be sorted by start time so that when we take a job, we can efficiently find the next non-overlapping job. Sorting by end time breaks the forward progression logic and makes binary search for the next valid job incorrect.

Off-by-One Errors in Binary Search

When finding the next non-overlapping job, the condition should be startTime[j] >= endTime[i] (using >= not >). Jobs that start exactly when another ends are non-overlapping. Using strict greater-than excludes valid job combinations and produces suboptimal results.

Forgetting to Handle the Skip Case

At each job, there are two choices: take it or skip it. A common mistake is only considering taking the job and recursing to the next non-overlapping position. You must also consider skipping the current job entirely with dfs(i + 1) and take the maximum of both options.

Using Linear Scan Instead of Binary Search

While a linear scan to find the next non-overlapping job produces correct results, it degrades the time complexity from O(n log n) to O(n^2). For large inputs, this causes time limit exceeded errors. Always use binary search to find the next valid job index.

Not Memoizing the Recursion

Without memoization, the recursive solution revisits the same subproblems exponentially many times. Each index can be reached through multiple paths, and recomputing the answer each time leads to exponential time complexity. Always cache the result for each index after computing it.

from typing import List

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        index = list(range(n))
        index.sort(key=lambda i: startTime[i])

        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            left, right, j = i + 1, n, n
            while left < right:
                mid = (left + right) // 2
                if startTime[index[mid]] >= endTime[index[i]]:
                    j = mid
                    right = mid
                else:
                    left = mid + 1

            dp[i] = max(dp[i + 1], profit[index[i]] + dp[j])

        return dp[0]

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<int> index(n), dp(n + 1, 0);
        for (int i = 0; i < n; i++) index[i] = i;
        sort(index.begin(), index.end(), [&](int i, int j) {
            return startTime[i] < startTime[j];
        });

        for (int i = n - 1; i >= 0; i--) {
            int left = i + 1, right = n, j = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[i] = max(dp[i + 1], profit[index[i]] + dp[j]);
        }

        return dp[0];
    }
};