zoj 3197

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3322

最小区间覆盖，排序加上贪心。

#include <iostream>   
#include <algorithm> 
#include <cstdio>
using namespace std;
struct SetNode{
	int a;
	int b;
}mySet[5010];
int n;
int minPoint;
int maxPoint;
bool cmp(SetNode a, SetNode b){
    if(a.a != b.a)
    	return a.a < b.a;
   	return a.b < b.b;
}
int work(){
   int cur = minPoint;
   int i = 0;
   int sum = 0;
   while(cur <= maxPoint && i < n){
      int temp = cur;
      while(cur >= mySet[i].a){
        if(temp < mySet[i].b)
		   temp =  mySet[i].b;
        i++;
	  }
	  cur = temp + 1;
	  sum++;
   }
   return sum;
}
int main(){
  int t;
  scanf("%d", &t);
  while(t--){
    scanf("%d", &n);
    minPoint = 1000000;
    maxPoint = -1;
    for(int i = 0; i < n; i++){
       scanf("%d%d", &mySet[i].a, &mySet[i].b);
       if(mySet[i].a < minPoint)
       	  minPoint = mySet[i].a;
 	   if(mySet[i].b > maxPoint)
 	      maxPoint = mySet[i].b;
	}
	sort(mySet, mySet + n, cmp);
	cout << work() << endl; 
  }
  
}