leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 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
通过次数
48.4K
提交次数
80.8K
通过率
59.9%


相关企业

提示 1
Think on DP.

提示 2
Sort the elements by starting time, then define the dp[i] as the maximum profit taking elements from the suffix starting at i.

提示 3
Use binarySearch (lower_bound/upper_bound on C++) to get the next index for the DP transition.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
startTime =
[1,2,3,3]
endTime =
[3,4,5,6]
profit =
[50,10,40,70]
Source