백준[2170] 선 긋기

문제 설명

문제 링크

http://icpc.me/2170

2170번: 선 긋기

풀이

스위핑 알고리즘을 이용하여 풀이 할 수 있다. 여기에 다른분이 잘 정리 해놨다.

수를 x좌표 기준으로 오름차순으로 정렬한 후 범위가 겹친다면 범위를 점차 늘려나가고, 겹치지 않을 때 그동안 늘려온 범위의 값을 더하며 새로운 범위를 시작한다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;

pii arr[1000006];

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
    sort(arr, arr + n);
    int l = -1e9, r = -1e9, ans = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i].first > r) {
            ans += r - l;
            l = arr[i].first;
            r = arr[i].second;
        }
        r = max(r, arr[i].second);
    }
    ans += r - l;
    printf("%d", ans);
}