练习题 No.3 区间调度问题（贪心法）

要求

有n项工作，每项工作分别在 Si 时间内开始，在 Ti 时间内结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全称参与。此外，参加工作的时间段不能重叠（即使是开始的瞬间和结束的瞬间的重叠也是不允许的）。 你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？

输入格式

第一行输入n 第二行输入n个s（开始时间） 第三行输入n个对应的t（结束时间）

输出格式

输出所参与的各个工作开始的时间，以空格分割每个开始时间，最后输出最多参与了多少项工作

测试输入

5 1 6 4 2 8 3 9 7 5 10

测试输出

1 4 8 3

解题思路

本题利用贪心法的思想。 1. 先将每个工作的时间从小到大排序（因为越早结束，说明你能干的工作越多）。 2. 遍历排序后的工作，依次判断能否开始参与即可。

代码

#include<iostream> #include<algorithm> #include<vector> using namespace std; bool Comp(pair<int, int> &a, pair<int, int> &b) { return a.second > b.second; } int main() { int n; vector<pair<int, int> > time; vector<int> startTime; cin >> n; for (int i = 0; i < n; i++) { pair<int, int> temp; cin >> temp.first; time.push_back(temp); } for (int j = 0; j < n; j++) { cin >> time[j].second; } sort(time.begin(), time.end()); int num = 0; int t = 0; for (int i = 0; i < n; i++) { if (time[i].first > t) { t = time[i].second; num++; startTime.push_back(time[i].first); } } vector<int>::iterator it; for (it = startTime.begin(); it != startTime.end(); it++) { cout << *it << " "; } cout << num << endl; return 0; }