编程练习（二）——调度所有区间

题目：蓄栏保留问题 总时间限制：1000ms 内存限制：65536kB 题目来源：OpenJudge

描述

农场有N头牛，每头牛会在一个特定的时间区间[A, B]（包括A和B）在畜栏里挤奶，且一个畜栏里同时只能有一头牛在挤奶。现在农场主希望知道最少几个畜栏能满足上述要求，并要求给出每头牛被安排的方案。对于多种可行方案，主要输出一种即可。

输入

输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000)，表示有N牛头；接下来N行每行包含两个数，分别表示这头牛的挤奶时间[Ai, Bi](1 ≤ A≤ B ≤ 1, 000, 000)。

输出

输出的第一行包含一个整数，表示最少需要的畜栏数；接下来N行，第i+1行描述了第i头牛所被分配的畜栏编号（从1开始）。

样例输入

5 1 10 2 4 3 6 5 8 4 7

样例输出

4 1 2 3 2 4

题解：C++

时间：243ms

#include <iostream> #include <queue> using namespace std; struct node_cow { int start, end;//区间开始时间和结束时间 int index;//牛的编号 friend bool operator < (node_cow a, node_cow b) { //start小的优先级高； return a.start > b.start; } }; struct node_end { int min_end; int num_class; friend bool operator <(node_end a, node_end b) { return a.min_end > b.min_end; } }; priority_queue<node_cow>nc; priority_queue<node_end>ne; int main() { int n; int num = 0; cin >> n; node_cow temp_nc; node_end temp_ne; int *r = new int[n]; for (int i = 0; i < n; i++) { cin >> temp_nc.start >> temp_nc.end; temp_nc.index = i; nc.push(temp_nc); } while (!nc.empty()) { temp_nc = nc.top(); nc.pop(); if (ne.empty()) {//如果已分配队列为空 num++; temp_ne.min_end = temp_nc.end; temp_ne.num_class = num; ne.push(temp_ne); r[temp_nc.index ] = num; } else { temp_ne = ne.top(); if (temp_nc.start <= temp_ne.min_end) {//分配新桶 num++; temp_ne.min_end = temp_nc.end; temp_ne.num_class = num; ne.push(temp_ne); r[temp_nc.index ] = num; } else { ne.pop(); temp_ne.min_end = temp_nc.end; ne.push(temp_ne); r[temp_nc.index ] = temp_ne.num_class; } } }//end while cout << num << endl; for (int i = 0; i < n; i++) cout << r[i] << endl; return 0; }

总结

这是一道调度所有区间使所用资源数达到最小的问题。首先对于区间按照开始时间依次递增排序，然后对已经分配的区间，记录最小结束时间的区间以及其所在的蓄栏。对于每一个未曾分配的区间，如果其开始时间不大于最小结束时间，那么需要分配新的资源（蓄栏），如果其开始时间大于最小结束时间，那么就不需要新的资源，把该区间分配给最小结束时间所在的资源，然后更新已分配资源最小结束时间。 需要注意的是，用优先队列可能才不至于超时。我第一次用了vector容器和sort排序函数，结果一直时间超限，最后用了优先队列才避免了这个问题。但是最终程序的时间也是243ms. 如果有更优的解法，希望朋友能分享给我，谢谢了。