LeetCode: Maximum Profit in Job Scheduling Posted on August 5, 2019July 26, 2020 by braindenny Maximum Profit in Job Scheduling Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #binarysearch, #dynamicprogramming 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 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: DP + binarysearch. (No need to store 2 states of take or skip) // https://code.dennyzhang.com/maximum-profit-in-job-scheduling // Basic Ideas: DP + binarysearch // // Sort jobs by ending time, instead of by starting time. // (This offers a big help for binarysearch approach) // Evaluate jobs one by one // // For each job, two possible actions: take or don't take // // dp(i, 0): don't take // dp(i, 1): take // How to get the result, when taking? // For all previous jobs, if overlapped with current one, skip // // The final result is the optimal one for all possible situations of dp(i,j) // // Complexity: Time O(n*log(n)), Space O(n) import "sort" type MyNode struct { s, e, p int } func max(x, y int) int { if x>y { return x } else { return y } } func jobScheduling(startTime []int, endTime []int, profit []int) int { nums := make([]MyNode, len(startTime)) for i, _ := range nums { nums[i] = MyNode{s:startTime[i], e:endTime[i], p:profit[i]} } sort.Slice(nums, func(i, j int) bool { return nums[i].e<nums[j].e }) dp := make([]int, len(nums)) // DP for i, _ := range nums { // Take // binary search left, right := 0, len(nums)-1 target := nums[i].s // may not exists // Find the last insert location for left<=right { // fmt.Println(left, right) mid := left+(right-left)/2 if nums[mid].e <= target { // drop left half left = mid+1 } else { right = mid-1 } } dp[i] = nums[i].p // right, left if right >= 0 { dp[i] += dp[right] } // don't take if i>0 { dp[i] = max(dp[i], dp[i-1]) } } return dp[len(dp)-1] } Solution: // https://code.dennyzhang.com/maximum-profit-in-job-scheduling // Basic Ideas: DP + binarysearch // // Sort jobs by ending time, instead of by starting time. // (This offers a big help for binarysearch approach) // Evaluate jobs one by one // // For each job, two possible actions: take or don't take // // dp(i, 0): don't take // dp(i, 1): take // How to get the result, when taking? // For all previous jobs, if overlapped with current one, skip // // The final result is the optimal one for all possible situations of dp(i,j) // // Complexity: Time O(n*log(n)), Space O(n) import "sort" type MyList []int var starts []int var profits []int func (a MyList) Len() int { return len(a) } func (a MyList) Less(i, j int) bool { if a[i] != a[j] { return a[i]<a[j] } else { return starts[i]<starts[j] } } func (a MyList) Swap(i, j int) { a[i], a[j] = a[j], a[i] starts[i], starts[j] = starts[j], starts[i] profits[i], profits[j] = profits[j], profits[i] } func max(x, y int) int { if x>y { return x } else { return y } } func jobScheduling(startTime []int, endTime []int, profit []int) int { starts = startTime profits = profit sort.Sort(MyList(endTime)) dp := make([]int, len(startTime)) res := 0 take, notake := 0, 0 // DP for i, _ := range dp { take2, notake2 := 0, 0 if i>0 { notake2 = max(take, notake) } // get dp[i][1] // binary search left, right := 0, len(endTime)-1 target := startTime[i] // may not exists // Find the last insert location for left<=right { // fmt.Println(left, right) mid := left+(right-left)/2 if endTime[mid] <= target { // drop left half left = mid+1 } else { right = mid-1 } } take2 = profit[i] // right, left if right >= 0 { take2 += dp[right] } take, notake = take2, notake2 dp[i] = max(take, notake) res = max(res, dp[i]) } return res } Post Views: 0