SDNU-1012.区间合并

##SDNU- 1012.区间合并

Description
给定n个开区间，合并他们中的重合者，输出合并后的区间数量。
Input
第一行：n(1 <= n <= 1000)
第2至第n+1行：每行两个整数(不会超过int)，第i行的两个整数表示第i-1个区间的左边界和右边界。
Output
合并后所剩余的区间数量。
Sample Input
3
1 3
2 5
6 7
Sample Output
2

这个看师哥的代码没看懂，然后看紫书的贪心的一些问题找到了一些思路，也不知道为什么以前的思路就是不对。
这题我就用了贪心思想。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <cstdio>
using namespace std;
struct inter
{
    int left,right;
    int flag=1;//用来标记被合并的区间
}a[1005];
bool cmp (inter x,inter y)
{
    if (x.left!=y.left)
        return x.left<y.left;
    return x.right<y.right;
}//排序，让区间按照其左端点排序。
bool judge(int x,int y)
{
    if (a[y].left>=a[x].right)
        return false;//排序使得判断更简单。
    return true;
}
void Union(int x,int y)
{
    a[y].flag=0;
    a[x].right=max(a[x].right,a[y].right);//结合也更简单。
}
int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i].left>>a[i].right;
    sort(a,a+n,cmp);
    for (int i=0;i<n-1;i++)
    {
        if (a[i].flag)
        {
            for (int j=i+1;j<n;j++)
                if (judge(i,j))
                    Union(i,j);
        }
    }
    int sum=0;
    for (int i=0;i<n;i++)
    {
        if (a[i].flag)
            sum++;
    }
    cout<<sum<<endl;
    return 0;
}