1235. Maximum Profit in Job Scheduling
https://leetcode.com/problems/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, 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^41 <= startTime[i] < endTime[i] <= 10^91 <= profit[i] <= 10^4
----
Intuition
No overlap => Next job should start after previous job has ended
Sort jobs by ending time
Need to find latest job just before current job starting time => Tree Map
Track the max profit against each end time
Initialize TreeMap 0, 0 => 0 end time => 0 profit
for each job
find entry with end time <= current start time. => TreeMap.floorEntry(current job start time)
next profit = TreeMap.floorEntry().getValue() + current profit
if next profit > max
save max
put current end time, max on map
---
Time - O(N log N)
Space - O(N)
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { | |
| int[][] jobs = new int[profit.length][3]; | |
| for (int i = 0; i < profit.length; i++) { | |
| jobs[i][0] = startTime[i]; | |
| jobs[i][1] = endTime[i]; | |
| jobs[i][2] = profit[i]; | |
| } | |
| // Sort by end time ascending | |
| Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1])); | |
| // Max profit at given end time | |
| TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); | |
| map.put(0, 0); | |
| int max = 0; | |
| for (int[] job: jobs) { | |
| int start = job[0]; | |
| // max profit from job ending before current start + current profit | |
| int next = map.floorEntry(start).getValue() + job[2]; | |
| if (next > max) { | |
| map.put(job[1], next); | |
| max = next; | |
| } | |
| } | |
| return max; | |
| } | |
| } |
