[백준] 10165 - 버스 노선 (c++)

KOI 2014 > 고등부 2번 문제이다.

https://www.acmicpc.net/problem/10165

 

문제 요약

N크기의 원형 공간에 각각 번호가 있는 구간 M개가 주어진다

다른 구간에 완전히 포함되지 않는 구간의 번호를 모두 출력해라

 

풀이  (MlogM)

• 스위핑

먼저 원형 문제를 선형 문제로 바꿀 수 있다.

공간을 0~N-1에서 0~N*2-1로 넓혀주면 a>b인 구간을 표현할 수 있고

a<b인 구간은 a~b, a+n~b+n구간으로 두 번 표현하면 된다.

 

어떤 구간이 다른 구간에 완전히 포함 되는지는 스위핑으로 쉽게 알아낼 수 있다.

시작점이 작은 순으로 정렬하고 순회하면서 끝점의 최댓값을 갱신하면, 끝점이 최댓값 보다 작을 땐 구간이 다른 구간에 완전히 포함된다. 단, 시작점이 같은 구간은 끝점이 큰 순으로 정렬해야 한다.

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n,m;cin >> n >> m;

    vector<array<int,3>> l;
    for(int i=1,a,b;i<=m;i++) {
        cin>>a>>b;
        if(a<b)
            l.push_back({a,b,i}),l.push_back({a+n,b+n,i});
        else
            l.push_back({a,b+n,i});
    }
    
    sort(l.begin(),l.end(),[&](array<int,3> a,array<int,3> b){
        if(a[0]==b[0])
            return a[1]>b[1];
        return a[0]<b[0];
    });

    bool ex[m+1]{0};
    int r=-1;
    for(auto x:l) {
        if(x[1]>r)
            r=x[1];
        else
            ex[x[2]]=1;
    }
    for(int i=1;i<=m;i++)
        if(!ex[i])
            cout << i<< ' ';
}