> For the complete documentation index, see [llms.txt](https://grind75-notes.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://grind75-notes.gitbook.io/notes/week-8/maximum-profit-in-job-scheduling.md).

# Maximum Profit in Job Scheduling

{% embed url="<https://leetcode.com/problems/maximum-profit-in-job-scheduling>" %}

### 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`.
>
> &#x20;
>
> **Example 1:**
>
> ![](https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png)
>
> <pre><code>Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
> <strong>Output: 120
> </strong><strong>Explanation: The subset chosen is the first and fourth job. 
> </strong>Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.
> </code></pre>
>
> **Example 2:**
>
> ![](https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png)
>
> <pre><code>Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
> <strong>Output: 150
> </strong><strong>Explanation:
> </strong>The subset chosen is the first, fourth and fifth job. 
> Profit obtained 150 = 20 + 70 + 60.
> </code></pre>
>
> **Example 3:**
>
> ![](https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png)
>
> <pre><code>Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
> <strong>Output: 6
> </strong></code></pre>

### Pseudocode

```
- initial attemp to solve via graph 
    - one tasks are connected to others
- optimal solution is combination of dfs and binary search
```

### Solution

```javascript
// from solution
// top down DP with memo
// https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/733167/thinking-process-top-down-dp-bottom-up-dp/
var jobScheduling = function (startTime, endTime, profit) {
  const jobs = new Array(startTime.length);
  const dp = new Map();

  // make a new array containing start, time and profit
  for (let i = 0; i < jobs.length; i++) {
    jobs[i] = [startTime[i], endTime[i], profit[i]];
  }

  // sort according to start time
  jobs.sort((a, b) => a[0] - b[0]);

  return dfs(0, jobs, dp);
};

function dfs(idx, jobs, dp) {
  // base condition
  if (idx === jobs.length) {
    return 0;
  }

  if (dp.has(idx)) {
    return dp.get(idx);
  }

  // pre
  // given this particular job idx, find the next idx that has a non-overlapping start time
  let next = binarySearch(idx, jobs);

  // recurse
  let inclProfit = jobs[idx][2] + (next === -1 ? 0 : dfs(next, jobs, dp));
  let exclProfit = dfs(idx + 1, jobs, dp);

  // post
  dp.set(idx, Math.max(inclProfit, exclProfit));
  return Math.max(inclProfit, exclProfit);
}

function binarySearch(idx, jobs) {
  let lo = idx + 1;
  let hi = jobs.length - 1;

  while (lo <= hi) {
    let mid = Math.floor(lo + (hi - lo) / 2);

    // returns the next job by comparing, mid start time to idx end time
    if (jobs[mid][0] >= jobs[idx][1]) {
      // if start time of prev is also equals or more than idx end time, continue seraching
      if (jobs[mid - 1][0] >= jobs[idx][1]) {
        hi = mid - 1;

        // if prev job start time is less than idx end time, return
      } else {
        return mid;
      }
    } else {
      lo = mid + 1;
    }
  }
  return -1;
}

```

### Time and Space Complexity

#### Time

* What did the code do
* Total -

#### Space

* What did the code do
* Total -


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://grind75-notes.gitbook.io/notes/week-8/maximum-profit-in-job-scheduling.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.