## Algorithm

Problem Name: 1235. Maximum Profit in Job Scheduling

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

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

```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`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
int[][] 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]);
Integer[] cache = new Integer[n];
return dfs(0, jobs, cache);
}

private int dfs(int idx, int[][] jobs, Integer[] cache) {
if (idx == jobs.length) {
return 0;
}
if (cache[idx] != null) {
return cache[idx];
}
int nextIdx = idx + 1;
while (nextIdx < jobs.length && jobs[idx][1] > jobs[nextIdx][0]) {
nextIdx++;
}
int jobScheduled = jobs[idx][2] + dfs(nextIdx, jobs, cache);
int jobNotScheduled = dfs(idx + 1, jobs, cache);
return cache[idx] = Math.max(jobScheduled, jobNotScheduled);
}
}
``````
Copy The Code &

Input

cmd
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output

cmd
120

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const jobScheduling = function (startTime, endTime, profit) {
const n = startTime.length
const items = Array(n)
for(let i = 0;i < n; i++) items[i] = [startTime[i], endTime[i], profit[i]]
items.sort((a, b) => a[1] - b[1])
const dpEndTime = [0]
const dpProfit = [0]
for(const [s, e, p] of items) {
const prevIdx = binarySearch(dpEndTime, 0, dpEndTime.length - 1, s)
const curProfit = dpProfit[prevIdx] + p, maxProfit = dpProfit[dpProfit.length - 1]
if(curProfit > maxProfit) {
dpProfit.push(curProfit)
dpEndTime.push(e)
}
}

return dpProfit[dpProfit.length - 1]
}

function binarySearch(arr, l, r, x) {
while (l < r) {
const mid = r - ((r - l) >> 1)
if (arr[mid] > x) r = mid - 1
else l = mid
}
return l
}
``````
Copy The Code &

Input

cmd
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output

cmd
120

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
dp = [[0, 0]]
for s, e, p in jobs:
i = bisect.bisect(dp, [s + 1]) - 1
if dp[i][1] + p > dp[-1][1]:
dp.append([e, dp[i][1] + p])
return dp[-1][1]
``````
Copy The Code &

Input

cmd
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output

cmd
150

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _1235_MaximumProfitInJobScheduling
{
public int JobScheduling(int[] startTime, int[] endTime, int[] profit)
{
var pairs = new (int start, int end, int profit)[profit.Length];
for (int i = 0; i < profit.Length; i++)
pairs[i] = (startTime[i], endTime[i], profit[i]);
Array.Sort(pairs, (a, b) => a.end.CompareTo(b.end));

var dpEndTime = new List();
var dpProfit = new List();

foreach (var pair in pairs)
{
var prevIndex = Array.BinarySearch(dpEndTime.ToArray(), pair.start + 1);
if (prevIndex < -1)
prevIndex = ~prevIndex;
prevIndex--;

var currentProfit = dpProfit[prevIndex] + pair.profit;
if (currentProfit > dpProfit[dpProfit.Count - 1])
{
}
}

return dpProfit[dpProfit.Count - 1];
}
}
}
``````
Copy The Code &

Input

cmd
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output

cmd
150