题目：规划兼职工作
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有n份兼职工作，每份工作预计从startTime[i]开始到endTime[i]结束，报酬为profit[i]。
给你一份兼职工作表，包含开始时间startTime，结束时间endTime和预计报
酬profit三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作。示例 1：
输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]输出：120
解释：
我们选出第 1 份和第 4 份工作，
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。
示例 2：
输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20, 100,70,60]
输出：150
解释：
我们选择第 1，4，5 份工作。
共获得报酬 150 = 20 + 70 + 60。
示例 3：
输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输出：6
提示：
•  1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
•  1 <= startTime[i] < endTime[i] <= 10^9
•  1 <= profit[i] <= 10^4
语言:cpp
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<vector<int>> q(n + 1);
for(int i = 1; i <= n; i ++) q[i] = {startTime[i - 1], endTime[i - 1], profit[i - 1]};
sort(q.begin() + 1, q.end(), [](const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
});
vector<int> f(n + 1);
for(int i = 1; i <= n; i ++) {
f[i] = f[i - 1];
int l = 0, r = i - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(q[mid][1] <= q[i][0]) l = mid;
else r = mid - 1;
}
f[i] = max(f[i], f[r] + q[i][2]);
}
return f[n];
}
};
语言:python3
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], p
rofit: List[int]) -> int:
# 将所有兼职组装为列表形式[[start, end, profit]]
jobs = list(zip(startTime, endTime, profit))
# 根据endTime排序这些兼职
jobs.sort(key=lambda x:x[1])
# 防止第一个兼职判断的时候越界，添加一个虚拟兼职，开始时间和结束时间还有收益都为0
jobs = [[0, 0, 0]] + jobs
n = len(startTime)
# 设置dp状态，总共n个真实兼职和1个虚拟兼职
dp = [0 for _ in range(n + 1)]
# 遍历每一个兼职
for i in range(1, n + 1):
cur = i
# 对于第i个兼职，查jobs[j][1] <= jobs[i][0]的第一个兼职，即逆序查兼职的结束时间刚好<=当前兼职开始时间的第一个兼职
for j in range(i - 1, -1, -1):
# 到了, 令cur=j，然后停止查，不到cur = i
if jobs[j][1] <= jobs[i][0]:
cur = j
break
# 当前的状态即为
# max(前一个状态的最大收益, 当前兼职的收益+之前到的前一个兼职状态的最大收益)
dp[i] = max(dp[i - 1], jobs[i][2] + dp[cur])
# 返回最后一个状态的收益
return dp[-1]
语言:java
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int len = startTime.length;
int[][] jobs = new int[len][3];
for (int i = 0; i < len; i++) {
jobs[i][0] = startTime[i];
jobs[i][1] = endTime[i];
jobs[i][2] = profit[i];
}
// dp[i]表示当前若参加第i个兼职时最大的报酬
int[] dp = new int[len+1];
dp[0] = 0;
Arrays.sort(jobs, (x, y) -> (x[1] - y[1]));
for (int i = 1; i <= len; i++) {
int last = getLast(jobs, i);
dp[i] = Math.max(dp[i-1], dp[last] + jobs[i-1][2]);
}
return dp[len];
}
private int getLast(int[][] jobs, int i) {
int last = 0;
for (int j = i-1; j >= 1; j--) {
if (jobs[j-1][1] <= jobs[i-1][0]) {
last = j;
System.out.println(last);
break;
}
}
return last;
}
}
语言:java
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int [][]events= new int[startTime.length][3];
for(int i=0;i<startTime.length;i++){
events[i][0]=startTime[i];
events[i][1]=endTime[i];
events[i][2]=profit[i];
}
Arrays.sort(events,new Comparator<int[]>() {
public int compare(int[] a, int[] b){
return a[1]-b[1];
}});
int g[]=new int[events.length];
for(int i=0;i<events.length;i++){
int left = 0;
int right = i-1;
while(left<=right){
int middle = (left + right )/2;
if(events[middle][1]>events[i][0]) right=middle-1;
else left=middle+1;
}
g[i] = events[i][2];
if(i>0){
if(right>-1) g[i] = g[i] + g[right];
g[i] = Math.max(g[i],g[i-1]);
}
}
return g[startTime.length-1];
}
}
语言:javascript
/**
python新手怎么兼职
* @param{number[]} startTime
* @param{number[]} endTime
* @param{number[]} profit
* @return {number}
*/
var jobScheduling =function(startTime, endTime, profit) {
let rides = [];
let n =-Infinity;
for (let i =0; i < startTime.length; i++) {
rides.push([startTime[i], endTime[i], profit[i]]);
n = Math.max(n, endTime[i]);
}
return maxTaxiEarnings(n, rides);
};
var maxTaxiEarnings =function(n, rides) {
rides = rides.sort((a,b) => a[1] - b[1]);
let dp =new Array(n +1).fill(0);
let index =0;
dp[0] =0;
for (let i =1; i < dp.length; i++) {
dp[i] = dp[i -1];
while ((index < rides.length) && (i == rides[index][1])) {
dp[i] = Math.max((dp[rides[index][0]] + rides[index][2]), dp[i -1], dp[i]);            index ++;
}
}
return dp[dp.length-1];
};
语言:php
class S olution {
/**
* @param Integer[] $startTime
* @param Integer[] $endTime
* @param Integer[] $profit
* @return Integer
*/
function jobScheduling($startTime,$endTime,$profit) {
$s_t = count($startTime);
$jobs = [];
for($i=0;$i<$s_t;$i++) {
$jobs[$i]['start'] = $startTime[$i];
$jobs[$i]['end'] = $endTime[$i];
$jobs[$i]['profit'] = $profit[$i];
}
usort($jobs,function($f,$n){
return$f['end'] > $n['end'];
});
//动态规划开始
$dp = [];
$dp[0] = $jobs[0]['profit'];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。