1235. Maximum Profit in Job Scheduling #

Problem #

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

Problem Summary #

You plan to use your free time to do part-time work and earn some pocket money. There are n part-time jobs here; each job is scheduled to start at startTime[i] and end at endTime[i], with a reward of profit[i]. You are given a part-time job list containing three arrays: start time startTime, end time endTime, and expected reward profit. Please calculate and return the maximum reward you can obtain. Note that 2 jobs whose times overlap cannot be performed at the same time. If a job you choose ends at time X, then you can immediately take the next job that starts at time X.

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solution Approach #

Given a set of tasks, each task has a start time, an end time, and a profit. Once a task starts and has not yet ended, no other tasks can be scheduled in between. How should the tasks be scheduled so that the final profit is maximized?
For typical task problems or interval problems, you usually consider whether sorting can be applied. For this problem, first sort the tasks by end time in ascending order; if the end times are the same, sort by profit in ascending order. dp[i] represents the maximum profit obtainable from the first i jobs. The initial value is dp[0] = job[1].profit. For any task i, check whether a j satisfying the condition jobs[j].enTime <= jobs[j].startTime && j < i can be found, that is, search for upper_bound. Since jobs has been sorted, binary search can be used here. If a task j satisfying the condition can be found, then the state transition equation is: dp[i] = max(dp[i-1], jobs[i].profit). If a task j satisfying the condition can be found, then the state transition equation is: dp[i] = max(dp[i-1], dp[low]+jobs[i].profit). The final answer is in dp[len(startTime)-1].

Code #


package leetcode

import "sort"

type job struct {
	startTime int
	endTime   int
	profit    int
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	jobs, dp := []job{}, make([]int, len(startTime))
	for i := 0; i < len(startTime); i++ {
		jobs = append(jobs, job{startTime: startTime[i], endTime: endTime[i], profit: profit[i]})
	}
	sort.Sort(sortJobs(jobs))
	dp[0] = jobs[0].profit
	for i := 1; i < len(jobs); i++ {
		low, high := 0, i-1
		for low < high {
			mid := low + (high-low)>>1
			if jobs[mid+1].endTime <= jobs[i].startTime {
				low = mid + 1
			} else {
				high = mid
			}
		}
		if jobs[low].endTime <= jobs[i].startTime {
			dp[i] = max(dp[i-1], dp[low]+jobs[i].profit)
		} else {
			dp[i] = max(dp[i-1], jobs[i].profit)
		}
	}
	return dp[len(startTime)-1]
}

type sortJobs []job

func (s sortJobs) Len() int {
	return len(s)
}
func (s sortJobs) Less(i, j int) bool {
	if s[i].endTime == s[j].endTime {
		return s[i].profit < s[j].profit
	}
	return s[i].endTime < s[j].endTime
}
func (s sortJobs) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}