POJ 1089 Intervals 區間覆蓋+ 貪心

題意：就是給你一些區間，若兩個區間能夠合並，則合並。求最後又多少個區間，輸出最後的區間。
思路：其實就是一個貪心的題目，不過要想做到1A還是有點困難的。有許多情況需要考慮清楚，我也是wa了幾次才過的。我們可以先按開始端點從小到大排序，若開始端點相等，則按結尾端點從小到大排序。排序之後能合並則合並。合並的時候有兩種情況，一種是起點和開始點的起點一樣，但是終點比開始點的終點大，這種情況需要考慮；另一種就是開始點小於等於起點的結束點。在合並的過程中，起點的結尾點需要一直不斷的更新。
代碼：
[cpp]www.2cto.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; 
}