LeetCode-Day32——依旧贪心
630. 课程表III
这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。
给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。
示例：
1
2
3
4
5
6
7
8
| 输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出: 3
解释:
这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。
|
提示:
1
2
| 整数 1 <= d, t, n <= 10,000 。
你不能同时修两门课程。
|
思路：
- 首先，按照以往的思路，先按照结束时间对课程进行排序
- 使用一个大顶堆来储存已经选择的课程的长度
- 一旦发现安排了当前课程之后，其结束时间超过了最晚结束时间，那么就从已经安排的课程汇总，取消掉一门最耗时的课程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
sort(courses.begin(), courses.end(), [](vector<int>& a, vector<int>& b) {
return a[1] < b[1];
});
priority_queue<int> q;
int dur = 0;
for(int i = 0;i < courses.size();i++) {
if(dur + courses[i][0] <= courses[i][1]) {
dur += courses[i][0];
q.push(courses[i][0]);
} else if(!q.empty() && q.top() > courses[i][0]) {
dur += (courses[i][0] - q.top());
q.pop();
q.push(courses[i][0]);
}
}
return q.size();
}
};
|
Tips
今日的小提示就是大顶堆，可以利用C++中已有的数据结构qriority_queue，基本操作也就是push(),pop()
714. 买卖股票的最佳时期含手续费
方法：动态规划
我们维护两个变量cash 和hold，前者表示当我们不持有股票时的最大利润（即卖出），后者表示当我们持有股票时的最大利润。
在第i天是，我们需要根据第i - 1天的装啊提来更新cash和hold的值。对于cash，我们可以保持不变，或者将手上的股票卖出，状态转移方程为：
cash = max(cash, hold + prices[i] - fee)
对于hold，我们可以保持不变，或者买入这一天的股票，状态转移方程为:
hold = max(hold, cash - prices[i])
在计算这两个状态转移方程时，我们可以不使用临时变量来存储cash和hold的值，而是可以先计算cash再计算hold，原因是在同一天卖出在买入（亏了一比手续费）一定不会比不进行任何操作好
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int cash = 0, hold = -prices[0];
for(int i = 1;i < prices.size();i++) {
cash = max(cash, hold + prices[i] - fee);
hold = max(hold, cash - prices[i]);
}
return cash;
}
};
|