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 * 1041 <= startTime[i] < endTime[i] <= 1091 <= 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);
}
}
Input
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output
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
}
Input
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output
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]
Input
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output
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 < int>();
var dpProfit = new List<int>();
dpEndTime.Add(0);
dpProfit.Add(0);
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])
{
dpProfit.Add(currentProfit);
dpEndTime.Add(pair.end); ;
}
}
return dpProfit[dpProfit.Count - 1];
}
}
}
Input
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output
150