POJ 1089 Intervals 区间覆盖+ 贪心

题意：就是给你一些区间，若两个区间能够合并，则合并。求最后又多少个区间，输出最后的区间。
思路：其实就是一个贪心的题目，不过要想做到1A还是有点困难的。有许多情况需要考虑清楚，我也是wa了几次才过的。我们可以先按开始端点从小到大排序，若开始端点相等，则按结尾端点从小到大排序。排序之后能合并则合并。合并的时候有两种情况，一种是起点和开始点的起点一样，但是终点比开始点的终点大，这种情况需要考虑；另一种就是开始点小于等于起点的结束点。在合并的过程中，起点的结尾点需要一直不断的更新。
代码：
[cpp]www.zzzyk.com
#include <iostream>
#include <cstdio>
#include <string.h>
#include <climits>
#include <algorithm>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 50010;
struct interval{
    int st,et;
}aa[N];
int flag[N];
bool cmp(interval a,interval b){
    if(a.st == b.st )
        return a.et < b.et;
    return a.st < b.st;
}
int max(int a,int b){
    return a > b ? a : b;
}
int main(){
    //freopen("1.txt","r",stdin);
    int n;
    while(scanf("%d",&n) != EOF){
        for(int i = 0;i < N; ++i){
          aa[i].st = aa[i].et = INT_MAX;
        }
        CLR(flag,0);
       for(int i = 0; i < n; ++i)
           scanf("%d%d",&aa[i].st,&aa[i].et);
       sort(aa,aa+n,cmp);
       int id;
       for(int i = 0; i < n; ){
          id = i;
          printf("%d ",aa[id].st);
          while(aa[i+1].st == aa[id].st){
             i++;
          }
          aa[id].et = aa[i].et;
          while(aa[i+1].st <= aa[id].et){
            i++;
            if(aa[i].et > aa[id].et)
                aa[id].et = aa[i].et;
          }
          if(aa[i].et > aa[id].et)
             aa[id].et = aa[i].et;
          printf("%d\n",aa[id].et);
          i++;
       }
    }
    return 0;
}

补充：软件开发 , C++ ,