Leetcode: Maximum Profit in Job Scheduling – Prepare For Coder Interview

Maximum Profit in Job Scheduling

Similar Problems:

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