# Maximum Profit in Job Scheduling
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-profit-in-job-scheduling)
Canonical: https://scaleengineer.com/dsa/problems/maximum-profit-in-job-scheduling
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [PayPal](https://scaleengineer.com/companies/paypal), [Snowflake](https://scaleengineer.com/companies/snowflake), [Zeta](https://scaleengineer.com/companies/zeta), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [oyo](https://scaleengineer.com/companies/oyo), [Pinterest](https://scaleengineer.com/companies/pinterest), [Verkada](https://scaleengineer.com/companies/verkada), [Urban Company](https://scaleengineer.com/companies/urban-company), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital), [WeRide](https://scaleengineer.com/companies/weride), [Pony.ai](https://scaleengineer.com/companies/pony.ai)
---
## 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 starts at time `X`.

**Example 1:**

**![](https://assets.glich.co/dsa/maximum-profit-in-job-scheduling/image0.png)**

**Input:** startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
**Output:** 120
**Explanation:** The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

**Example 2:**

**![](https://assets.glich.co/dsa/maximum-profit-in-job-scheduling/image1.png)** 

**Input:** startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
**Output:** 150
**Explanation:** The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

**Example 3:**

**![](https://assets.glich.co/dsa/maximum-profit-in-job-scheduling/image2.png)**

**Input:** startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
**Output:** 6

**Constraints:**

* `1 <= startTime.length == endTime.length == profit.length <= 5 * 104`
* `1 <= startTime[i] < endTime[i] <= 109`
* `1 <= profit[i] <= 104`

# Approaches
## Brute-Force Recursion
This approach explores all possible valid subsets of jobs. For each job, we make a decision: either to include it in our set or to skip it. This generates a decision tree of possibilities. We then find the path in this tree that yields the maximum total profit. While simple to understand, it is highly inefficient.
**Time:** O(n * 2^n). The recursion tree can have up to 2^n nodes. In each node, we might do a linear scan to find the next job, which takes O(n) time. Sorting takes an initial O(n log n). The overall complexity is dominated by the exponential nature of the recursion. · **Space:** O(n), for the recursion call stack depth in the worst case.
**Pros:** Simple to conceptualize and implement.; Directly translates the problem statement into a recursive structure.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.; Performs a large number of redundant computations for the same subproblems.
### Explanation
The brute-force method systematically checks every combination of jobs. We can model this using recursion.

First, we combine the `startTime`, `endTime`, and `profit` arrays into a single structure, a `Job` object, for easier handling. To make the decision process more structured, we sort these jobs based on their `startTime`.

A recursive function, let's call it `findMaxProfit(index)`, is the core of this approach. This function calculates the maximum profit obtainable from the sub-array of jobs starting from `index`.

For any given `job[index]`, we face two choices:
1.  **Skip the job:** We don't take `jobs[index]`. The maximum profit is then whatever we can make from the remaining jobs, which is found by recursively calling `findMaxProfit(index + 1)`.
2.  **Take the job:** We add `jobs[index].profit` to our total. Since we cannot take any overlapping jobs, we must then find the first subsequent job that starts at or after the current job's `endTime`. Let's say this is at `nextIndex`. We then add the result of `findMaxProfit(nextIndex)` to our current job's profit.

The function returns the maximum profit from these two choices. The process starts with `findMaxProfit(0)`.

```java
class Solution {
    class Job {
        int start, end, profit;
        Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> a.start - b.start);
        return findMaxProfit(jobs, 0);
    }

    private int findMaxProfit(Job[] jobs, int index) {
        if (index >= jobs.length) {
            return 0;
        }

        // Option 1: Exclude current job
        int profit1 = findMaxProfit(jobs, index + 1);

        // Option 2: Include current job
        // Find the next non-overlapping job by linear scan
        int nextIndex = jobs.length;
        for (int j = index + 1; j < jobs.length; j++) {
            if (jobs[j].start >= jobs[index].end) {
                nextIndex = j;
                break;
            }
        }
        int profit2 = jobs[index].profit + findMaxProfit(jobs, nextIndex);

        return Math.max(profit1, profit2);
    }
}
```
### Algorithm
- Create a `Job` class to encapsulate `startTime`, `endTime`, and `profit`.
- Create an array of `Job` objects from the input arrays.
- Sort the `Job` array based on `startTime` to process jobs in chronological order.
- Define a recursive function `solve(index)` that calculates the maximum profit from jobs `index` to `n-1`.
- In `solve(index)`:
  - **Base Case:** If `index` is out of bounds, return 0.
  - **Recursive Step:** Explore two choices for `jobs[index]`:
    1. **Exclude:** The profit is `solve(index + 1)`.
    2. **Include:** The profit is `jobs[index].profit` plus the result of `solve(nextIndex)`, where `nextIndex` is the first job that starts after `jobs[index]` ends.
  - Return the maximum of the two choices.
- The initial call is `solve(0)`.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by eliminating redundant calculations. The recursive function often recalculates the maximum profit for the same subset of remaining jobs. By storing (memoizing) the result for each subproblem (i.e., for each starting `index`), we can look it up instead of recomputing it. This technique is known as top-down dynamic programming and significantly improves efficiency.
**Time:** O(n log n). Sorting the jobs takes O(n log n). The recursive function is called once for each index `i`, and inside each call, we perform a binary search which takes O(log n). The total time is O(n log n) + O(n log n) = O(n log n). · **Space:** O(n), required for the memoization array and the recursion stack.
**Pros:** Significantly more efficient than brute-force, with a polynomial time complexity.; Guaranteed to find the optimal solution.; The logic is a natural and intuitive extension of the recursive solution.
**Cons:** May cause a `StackOverflowError` for very deep recursion paths, though the problem constraints are generally manageable.; Slightly higher overhead than the iterative bottom-up approach due to recursive function calls.
### Explanation
The key observation to optimize the brute-force approach is that the subproblem `findMaxProfit(index)` is solved multiple times with the same input. We can avoid these re-computations by storing the result the first time we solve it and reusing it later.

We use a memoization array, `memo`, where `memo[i]` stores the maximum profit that can be obtained from the jobs in the range `[i, n-1]`. The array is initialized with -1 to signify that no subproblem has been solved yet.

The recursive function `findMaxProfit(index, memo)` is modified as follows:
1.  Before any computation, it checks `memo[index]`. If a value is already stored, it returns it immediately.
2.  If not, it computes the result just like the brute-force approach.
3.  To further optimize, finding the next non-overlapping job is done using binary search on the sorted `startTime`s, which reduces this step's complexity from O(n) to O(log n).
4.  Once the result is computed, it's stored in `memo[index]` before being returned.

```java
class Solution {
    class Job {
        int start, end, profit;
        Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> a.start - b.start);
        
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        
        return findMaxProfit(jobs, 0, memo);
    }

    private int findMaxProfit(Job[] jobs, int index, int[] memo) {
        if (index >= jobs.length) {
            return 0;
        }
        if (memo[index] != -1) {
            return memo[index];
        }

        // Option 1: Exclude current job
        int profit1 = findMaxProfit(jobs, index + 1, memo);

        // Option 2: Include current job
        int nextIndex = findNextJob(jobs, jobs[index].end, index + 1);
        int profit2 = jobs[index].profit + findMaxProfit(jobs, nextIndex, memo);

        return memo[index] = Math.max(profit1, profit2);
    }

    // Using binary search to find the next non-overlapping job
    private int findNextJob(Job[] jobs, int lastEndTime, int startIndex) {
        int low = startIndex, high = jobs.length - 1;
        int nextIndex = jobs.length;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (jobs[mid].start >= lastEndTime) {
                nextIndex = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return nextIndex;
    }
}
```
### Algorithm
- Create and sort an array of `Job` objects by `startTime`.
- Create a memoization array `memo` of size `n`, initialized to a value like -1.
- Define a recursive function `solve(index, memo)`.
- In `solve(index, memo)`:
  - **Base Case:** If `index >= n`, return 0.
  - **Memoization Check:** If `memo[index]` is not -1, return the stored value.
  - **Recursive Step:**
    1. **Exclude:** Calculate profit by calling `solve(index + 1, memo)`.
    2. **Include:** Calculate profit as `jobs[index].profit + solve(nextIndex, memo)`. Find `nextIndex` (the first job starting after the current one ends) efficiently using binary search.
  - Store the maximum of the two options in `memo[index]` before returning.

## Bottom-Up Dynamic Programming with Binary Search
This is an iterative version of the dynamic programming solution, which avoids recursion and the associated risk of stack overflow. We build the solution from the ground up. A common and elegant way to implement this is to sort the jobs by their end times and calculate the maximum profit iteratively.
**Time:** O(n log n). Sorting by `endTime` takes O(n log n). The main loop runs `n` times, and each iteration involves a binary search that takes O(log n) time. The total time complexity is dominated by these two parts, resulting in O(n log n). · **Space:** O(n), for storing the `Job` objects and the `dp` array.
**Pros:** Highly efficient and considered the standard optimal solution.; Avoids recursion, eliminating the risk of stack overflow and reducing function call overhead.; Iterative approach can have better performance due to cache locality.
**Cons:** The logic, especially the binary search on a growing prefix of end times, can be slightly less intuitive to grasp initially compared to the top-down approach.
### Explanation
The bottom-up DP approach builds the solution iteratively, which is often more efficient in practice and avoids recursion depth limits. A particularly clean implementation involves sorting the jobs by their `endTime`.

Let `dp[i]` be the maximum profit we can achieve by considering only the first `i+1` jobs (from index 0 to `i` in the `endTime`-sorted array). We iterate through the sorted jobs and for each job `i`, we determine `dp[i]`.

For each job `i`, we have two choices:
1.  **Exclude `jobs[i]`:** If we don't take the current job, the maximum profit remains the same as the maximum profit achievable using the first `i` jobs. This value is `dp[i-1]` (for `i > 0`).
2.  **Include `jobs[i]`:** The profit from this choice is `jobs[i].profit` plus the maximum profit from any non-overlapping previous jobs. A previous job `j` is non-overlapping if it finishes before `jobs[i]` starts (i.e., `jobs[j].endTime <= jobs[i].startTime`). We need to find the maximum profit from all such compatible jobs. Since our `dp` array is non-decreasing (because `dp[i]` is always at least `dp[i-1]`), we only need to find the latest compatible job `j` and add `dp[j]` to our current profit. This latest compatible job `j` can be found efficiently using binary search on the `endTime`s of jobs `0` to `i-1`.

The recurrence relation becomes: `dp[i] = max(dp[i-1], jobs[i].profit + dp[latest_compatible_job_index])`.

The final answer is `dp[n-1]`, which represents the maximum profit considering all jobs.

```java
class Solution {
    class Job {
        int start, end, profit;
        Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        // Sort jobs by end time
        Arrays.sort(jobs, (a, b) -> a.end - b.end);

        // dp[i] will be the maximum profit using jobs from 0 to i
        int[] dp = new int[n];
        dp[0] = jobs[0].profit;

        for (int i = 1; i < n; i++) {
            int profitIncludingCurrent = jobs[i].profit;
            int lastCompatibleJobIndex = -1;

            // Binary search to find the latest job that finishes before the current one starts
            int low = 0, high = i - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (jobs[mid].end <= jobs[i].start) {
                    lastCompatibleJobIndex = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            if (lastCompatibleJobIndex != -1) {
                profitIncludingCurrent += dp[lastCompatibleJobIndex];
            }

            // dp[i] is the max of including this job or not including it
            int profitExcludingCurrent = dp[i - 1];
            dp[i] = Math.max(profitIncludingCurrent, profitExcludingCurrent);
        }

        return dp[n - 1];
    }
}
```
### Algorithm
- Create and sort an array of `Job` objects by their `endTime`.
- Create a DP array, `dp`, of size `n`. `dp[i]` will store the maximum profit achievable considering a subset of the first `i+1` jobs.
- Initialize `dp[0] = jobs[0].profit`.
- Iterate from `i = 1` to `n-1`:
  - Calculate the profit if `jobs[i]` is included: `profitIncludingCurrent = jobs[i].profit`.
  - Find the latest compatible job `j < i` (where `jobs[j].endTime <= jobs[i].startTime`) using binary search on the `endTime`s of jobs `0` to `i-1`.
  - If such a job `j` exists, add its maximum profit: `profitIncludingCurrent += dp[j]`.
  - The maximum profit if `jobs[i]` is excluded is `dp[i-1]`.
  - Set `dp[i] = max(profitIncludingCurrent, dp[i-1])`.
- The final answer is `dp[n-1]`.

# Solutions
### Java

```java
class Solution {
private
  int[][] jobs;
private
  int[] f;
private
  int n;
public
  int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    n = profit.length;
    jobs = new int[n][3];
    for (int i = 0; i < n; ++i) {
      jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
    }
    Arrays.sort(jobs, (a, b)->a[0] - b[0]);
    f = new int[n];
    return dfs(0);
  }
private
  int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != 0) {
      return f[i];
    }
    int e = jobs[i][1], p = jobs[i][2];
    int j = search(jobs, e, i + 1);
    int ans = Math.max(dfs(i + 1), p + dfs(j));
    f[i] = ans;
    return ans;
  }
private
  int search(int[][] jobs, int x, int i) {
    int left = i, right = n;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (jobs[mid][0] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int jobScheduling(vector<int> &startTime, vector<int> &endTime,
                    vector<int> &profit) {
    int n = profit.size();
    vector<tuple<int, int, int>> jobs(n);
    for (int i = 0; i < n; ++i)
      jobs[i] = {startTime[i], endTime[i], profit[i]};
    sort(jobs.begin(), jobs.end());
    vector<int> f(n);
    function<int(int)> dfs = [&](int i) -> int {
      if (i >= n)
        return 0;
      if (f[i])
        return f[i];
      auto [_, e, p] = jobs[i];
      tuple<int, int, int> t{e, 0, 0};
      int j = lower_bound(jobs.begin() + i + 1, jobs.end(), t,
                          [&](auto &l, auto &r) -> bool {
                            return get<0>(l) < get<0>(r);
                          }) -
              jobs.begin();
      int ans = max(dfs(i + 1), p + dfs(j));
      f[i] = ans;
      return ans;
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int: @ cache def dfs(i): if i >= n: return 0 _, e, p = jobs[i] j = bisect_left(jobs, e, lo=i + 1, key=lambda x: x[0]) return max(dfs(i + 1), p + dfs(j)) jobs = sorted(zip(startTime, endTime, profit)) n = len(profit) return dfs(0)

```