NOI: 7062 구간 통합

전송:https://blog.csdn.net/loi_black/article/details/52874488
제목:http://noi.openjudge.cn/ch0204/7620/
Description n 개의 폐 구간 [ai; bi] 을 정 합 니 다. 그 중에서 i = 1, 2,..., n.임의의 두 개의 인접 하거나 교차 하 는 폐 구간 은 하나의 폐 구간 으로 합 칠 수 있다.예 를 들 어 [1; 2] 와 [2; 3] 는 [1; 3], [1; 3] 과 [2; 4] 를 [1; 4] 로 합병 할 수 있 지만 [1; 2] 와 [3; 4] 는 합병 할 수 없다.
우리 의 임 무 는 이 구간 들 이 최종 적 으로 하나의 폐 구간 으로 합 쳐 질 수 있 는 지 를 판단 하 는 것 이다. 만약 가능 하 다 면 이 폐 구간 을 출력 하 는 것 이다. 그렇지 않 으 면 no 를 출력 하 는 것 이다.
Input 첫 번 째 행위 1 개 정수 n, 3 ≤ n ≤ 50000.입력 구간 의 수량 을 나타 낸다.이후 n 행 은 i 행 (1 ≤ i ≤ n) 에서 두 개의 정수 ai 와 bi 이 고 정수 간 에 하나의 빈 칸 으로 구분 하여 구간 [ai; bi] (그 중 1 ≤ ai ≤ bi ≤ bi ≤ 10000) 을 나타 낸다. Output 한 줄 을 출력 합 니 다. 이 구간 이 최종 적 으로 닫 힌 구간 으로 합 쳐 질 수 있다 면 이 닫 힌 구간 의 좌우 경 계 를 출력 하고 하나의 빈 칸 으로 분리 합 니 다.그렇지 않 으 면 no 를 출력 합 니 다. Sample Input 5 5 6 1 5 10 10 6 9 8 10 Sample Output 1 10
sort 후 욕심, 현재 업데이트 할 수 있 는 지 판단, 업데이트 할 수 있 으 면 업데이트, 출력 no.
코드 는 다음 과 같 습 니 다:

#include
#include
#include
#include
using namespace std;
const int maxn=100005;
struct dqs
{
    int x,y;
}hh[maxn];
bool flag=0;
bool cmp(dqs a,dqs b)
{
    if(a.x==b.x)
        return a.yreturn a.xint main()
{
    int ans=1;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&hh[i].x,&hh[i].y);
    sort(hh+1,hh+n+1,cmp);
    int l=hh[1].x,r=hh[1].y;
    for(int i=2;i<=n;i++)
    {
        if(hh[i].x<=r)
        {
            if(hh[i].y>r)
                r=hh[i].y;
        }
        else
        {
            printf("no
");
            flag=1;
            break;
        }
    }
    if(flag==0)
        printf("%d %d",l,r);
    return 0;
}