선분 합집합의 길이¶

직선 위에 $n$개의 선분이 주어지며, 각 선분은 좌표 쌍 $(a_{i1}, a_{i2})$로 표현됩니다. 이 선분들의 합집합의 길이를 구해야 합니다.

다음 알고리즘은 1977년 Klee가 제안하였습니다. 이 알고리즘은 $O(n\log n)$에 동작하며, 점근적으로 최적임이 증명되었습니다.

풀이¶

모든 선분의 끝점을 값 기준으로 정렬하여 배열 $x$에 저장합니다. 그리고 추가로 각 끝점이 선분의 왼쪽 끝인지 오른쪽 끝인지도 저장합니다. 이제 현재 열려 있는 선분의 개수를 세는 카운터 $c$를 유지하면서 배열을 순회합니다. 현재 원소가 왼쪽 끝이면 이 카운터를 증가시키고, 그렇지 않으면 감소시킵니다. 답을 계산하기 위해, 새로운 좌표에 도달할 때마다 현재 열려 있는 선분이 하나 이상 있으면 마지막 두 $x$ 값 사이의 길이 $x_i - x_{i-1}$을 더합니다.

구현¶

int length_union(const vector<pair<int, int>> &a) {
    int n = a.size();
    vector<pair<int, bool>> x(n*2);
    for (int i = 0; i < n; i++) {
        x[i*2] = {a[i].first, false};
        x[i*2+1] = {a[i].second, true};
    }

    sort(x.begin(), x.end());

    int result = 0;
    int c = 0;
    for (int i = 0; i < n * 2; i++) {
        if (i > 0 && x[i].first > x[i-1].first && c > 0)
            result += x[i].first - x[i-1].first;
        if (x[i].second)
            c--;
        else
            c++;
    }
    return result;
}