라인 스위핑

라인 스위핑은 수 직선 위의 여러 선분이 겹쳐있을 때, 이 선분을 모두 겹친 경우의 길이를 측정하는 알고리즘이다. 선분을 입력받을 때마다 그 길이를 측정해 합을 구한다면 선분이 겹쳤을 때 에러가 발생하므로 불가능하고, 선분을 입력받을 때마다 배열에 선분을 그린 뒤 길이를 센다면 선분의 길이 n에 대해 각 선분을 표시할 때의 시간 복잡도가 O(n)이므로 선분이 매우 길거나 선분의 개수가 매우 많다면 시간을 너무 오래 소모하게 된다.

{int crd, int stat}꼴 구조체의 배열 arr에 선분을 입력받을 때마다 {시작 좌표, 1}과 {끝 좌표, -1}을 push한 뒤 좌표가 증가하는 순으로, 좌표가 같다면 시작 좌표가 앞에 오게끔 정렬한다. 이후 arr을 0번째 인덱스부터 순차적으로 탐색하며 stat 값을 모두 더한다면, 그 값이 0이 되는 순간 수 직선에서 겹친 선분이 끝나므로, 이 때의 arr의 인덱스를 k라고 한다면 수 직선에 나타난 합쳐진 선분의 길이는 arr[k].crd - arr[0].crd가 된다. 이 과정을 k + 1부터 arr의 모든 성분에 대해 반복하게 되면 수 직선에 나타난 각 합쳐진 선분에 대해 길이를 구할 수 있다.

for (int i = 0; i < N; i++) {
cin >> a >> b;
    arr[2 * i] = {a, 1};
    arr[2 * i + 1] = {b, -1};
}

sort(arr, arr + (N *= 2));

for (int i = 0; i < N; i++) {
    if (!line) start = arr[i]._crd;
    line += arr[i]._stat;
    if (!line) ans += arr[i]._crd - start;
}

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

15922번: 아우으 우아으이야!!

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

19598번: 최소 회의실 개수