LeetCode [1235] Maximum Profit in Job Scheduling

 1235. Maximum Profit in Job Scheduling

Hard

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, you need to output the maximum profit you can take such that there are no 2 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 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class Solution { class Job{ int start; int end; int profit; Job(int s, int e, int p){ start = s; end = e; profit = p; } } Job[] jobs; int n; int getLastEndBefore(int t){ int l=0, r=n-1; while(l<=r){ int m = (l+r)/2; if(jobs[m].end<=t && (m==n-1 || jobs[m+1].end>t)) return m; if(jobs[m].end>t) r = m-1; else l = m+1; } return -1; } public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { n = startTime.length; jobs = new Job[n]; for(int i=0; i<n; ++i) jobs[i] = new Job(startTime[i], endTime[i], profit[i]); Arrays.sort(jobs, Comparator.comparingInt(j -> j.end)); int[] dp = new int[n]; int maxP = 0; for(int i=0; i<n; ++i){ int last = getLastEndBefore(jobs[i].start); dp[i] = jobs[i].profit; for(int j=last; j>=0; --j){ dp[i] = Math.max(dp[i], jobs[i].profit+dp[j]); if(jobs[j].end<=jobs[last].start) break; } maxP = Math.max(maxP, dp[i]); } return maxP; } }