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;
}