http://hihocoder.com/contest/hiho155/problem/1
思路：贪心。按时间先后顺序挨个处理任务，如果不用增加机器（当前开了的机器中有空闲的），就选出一个空闲的机器并更新该机器下一个空闲时刻；否则开一台新的机器。
算法：
- 开一个
multiset，维护当前所有机器空闲的时刻 - 对所有任务按开始时间从小到大排序，遍历任务：
- 在
multiset中找是否有小于等于当前任务开始时刻的值（意思就是当这个任务开始时，是否有机器空闲）。如果没有，则往multiset中插入当前任务的结束时刻，即加一台机器；如果有多个，选最大的那个，更新它的值为当前任务的结束时刻（删除它再插入当前任务的结束时刻。其实选哪个应该都可以，这么做对后面没有影响，但是选最大的把较早空闲的留着肯定是最保险的）
复杂度：排序O(nlogn)，遍历任务+multiset的操作：O(nlogn)，总复杂度O(nlogn)
注意点：
- 对于
multiset，要删除某一个元素时，不能erase键值，而是erase指向那个元素的迭代器，否则会把所有等于该键值的元素都删去 - 操作容器的迭代器时，一定要注意其合法性，避免越界
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <cstdlib> #include <string> #include <map> #include <set> using namespace std;int N; vector<pair<int, int>> tasks;void solve() {sort(tasks.begin(), tasks.end());multiset<int> machine;multiset<int>::iterator it;for (int i = 0; i < tasks.size(); ++i) {int s = tasks[i].first, e = tasks[i].second;if (machine.empty()) {machine.insert(e);} else {it = machine.lower_bound(s);if (it != machine.end()) {if (*it == s) {machine.erase(it);machine.insert(e);} else {if (it == machine.begin()) {machine.insert(e);} else {it--;if (*it <= s) {machine.erase(it);machine.insert(e);}}}} else {it = machine.end(); it--;machine.erase(it);machine.insert(e);}}}cout << machine.size() << endl; }int main() {cin >> N;tasks.resize(N);int s, e;for (int i = 0; i < N; ++i) {scanf("%d%d", &s, &e);tasks[i] = make_pair(s, e);}solve(); }