(贪心5.2.9)UVA 10020 Minimal coverage(利用数据有序化来进行贪心选择)

/* * UVA_10020.cpp * *  Created on: 2013年10月11日 *      Author: Administrator */#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn = 100005;struct line {int l;int r;bool operator<(const line& n) const{if( l != n.l){return l < n.l;}else{return r > n.r;}}}lines[maxn];int main() {int t;scanf("%d", &t);while (t--) {line s[maxn];int m;scanf("%d", &m);int l, r;int now=0, len=0, num = 0, ans = 0;while (scanf("%d%d", &l, &r) != EOF, l || r) {lines[num].l = l;lines[num++].r = r;}sort(lines,lines+num);int i;int k;bool flag =false;for (i = 0; i < num; ++i) {if(lines[i].l > now){flag = false;break;}if(lines[i].r > now){if(lines[i].r > len){len = lines[i].r;k = i;}if(lines[i+1].l > now || i + 1 == num){now = len;len = 0;s[ans++] = lines[k];}}if(now >= m){flag = true;break;}}if(!flag){printf("0\n");}else{printf("%d\n",ans);for(i = 0 ; i < ans ; ++i){printf("%d %d\n",s[i].l,s[i].r);}}if(t){printf("\n");}}return 0;}