PIPIOJ 1323: 区间合并 贪心

题目：

http://39.106.164.46/problem.php?id=1323

思路：

贪心。将左端点按照从小到大排序，然后依次比较合并区间即可。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define MAX 100005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

struct node{
    int x,y;
    bool operator < (const node &a) const{
        return x<a.x;
    }
};

int n;
node a[MAX];

int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d %d",&a[i].x,&a[i].y);
        }
        sort(a,a+n);
        node ans[n+1];
        ans[0].x=a[0].x,
        ans[0].y=a[0].y;
        int cnt=0;
        for(int i=1;i<n;i++){
            if(ans[cnt].y>=a[i].x&&ans[cnt].y<a[i].y){
                ans[cnt].y=a[i].y;
            }else if(ans[cnt].y<a[i].x){
                ans[++cnt].x=a[i].x;
                ans[cnt].y=a[i].y;
            }
        }
        printf("%d\n",cnt+1);
        for(int i=0;i<=cnt;i++){
            printf("%d %d\n",ans[i].x,ans[i].y);
        }
    }
    return 0;
}