## Problem

**Problem ID**: 1352

**Title**: Maximum Profit in Job Scheduling

**Difficulty**: Hard

**Description**:

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:**

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

**Example 2:**

** **

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

**Example 3:**

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

**Constraints:**

`1 <= startTime.length == endTime.length == profit.length <= 5 * 10`

^{4}`1 <= startTime[i] < endTime[i] <= 10`

^{9}`1 <= profit[i] <= 10`

^{4}

## Thoughts

This question is similar to 1851 where you need to use DP to optimise for both value and end time. Tried to use `size_t`

for all indexes but it leads to integer underflow and had to add an underflow check before `-1`

. Not sure what is the cleaner way to do binary search with `size_t`

.

## Solution

**General Idea**

We treat all `endTime`

s as the only possible times in the problem. When deciding on whether or not to choose a job, we can either choose it with the best possible combinations of jobs with `endTime < starTime`

or not choose it and have the profit set to the previously calculated best combinations of jobs.

**DP State**: `dp[i]`

- represents the best profit as of `jobs[i].endTime`

**DP transitions**: We can either

- Drop the current job:
`dp[i] = dp[i-1]`

- Choose the current job:
`dp[i] = dp[k] + jobs[i].profit`

where`k`

is the largest index such that`jobs[k].endTime <= jobs[i].startTime`

### Implementation

```
struct Job {
int start;
int end;
int profit;
};
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
auto n = startTime.size();
vector<Job> jobs(n);
for (size_t i = 0; i < n; i++) {
jobs[i] = {startTime[i], endTime[i], profit[i]};
}
sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b) { return a.end < b.end; });
vector<int> dp(n, 0);
for (auto i = 0; i < n; i++) {
int prev_profit = i > 0 ? dp[i-1] : 0;
const auto [start, end, profit] = jobs[i];
size_t l = 0;
size_t r = n-1;
while (l < r) {
size_t m = (l+r + 1)/2;
if (jobs[m].end <= start) {
l = m;
} else {
r = m;
if (r != 0) r--;
}
}
int curr_profit = profit;
if (jobs[l].end <= jobs[i].start) curr_profit += dp[l];
dp[i] = max(curr_profit, prev_profit);
}
return dp[n-1];
}
};
```