문제 29
전체 선분 길이
수직선 위에 $N$개의 선분이 있다.
하나 이상의 선분이 덮고 있는 구간의 길이를 구하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 각 선분의 왼쪽 끝점과 오른쪽 끝점의 좌표를 의미하는 두 정수 $l$, $r$이 공백으로 구분되어 주어진다. $(-10^9 \le l < r \le 10^9)$
출력
하나 이상의 선분이 덮고 있는 구간의 길이를 출력한다.
예제 입력 1
5 1 5 2 7 10 13 12 15 20 21
예제 출력 1
12
공식 해설
선분을 왼쪽 끝점이 작은 순서로 정렬하고, 겹치는 선분들을 하나의 구간으로 합친다.
현재 합친 구간을 $[L,R]$, 다음 선분을 $[l,r]$라 하자. $l\le R$이면 서로 닿거나 겹치므로 오른쪽 끝을 $\max(R,r)$로 늘린다. $l>R$이면 현재 구간과 떨어져 있다. 이후 선분의 왼쪽 끝도 $l$ 이상이므로 현재 구간을 더 늘릴 수 없고, 길이 $R-L$을 답에 더한 뒤 $[l,r]$로 새 구간을 시작한다.
모든 선분을 처리한 뒤 마지막 구간의 길이도 더한다. 이렇게 얻은 구간들은 서로 겹치지 않으며 원래 선분의 합집합과 같으므로 길이의 합이 정답이다.
시간복잡도는 $O(N\log(N+1))$, 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
선분을 vector<pair<long long, long long>>에 저장하고 sort하면 왼쪽 끝점부터 정렬된다. 현재 구간의 양 끝과 누적 길이를 long long으로 저장한다.
C 구현
끝점을 담은 구조체 배열을 왼쪽 끝점 순으로 qsort한다. 현재 오른쪽 끝점보다 다음 왼쪽이 크면 이전 길이를 더한다. 좌표 차이는 최대 $2 \cdot 10^{9}$이며 전체 길이는 long long으로 누적한다.
Python 구현
(l, r) 튜플을 sort()한 뒤 현재 병합 구간의 양 끝과 누적 길이를 저장한다.
Java 구현
Comparator.comparingLong으로 왼쪽 좌표를 비교하여 정렬하고 끝점과 합은 long으로 계산한다.
Rust 구현
(i64, i64) 튜플 Vec을 sort_unstable()로 정렬한다. 다음 왼쪽 끝점이 현재 오른쪽보다 클 때만 구간을 닫는다. 최종 길이 계산에도 부호 있는 i64를 사용한다.
JavaScript 구현
선분은 [l, r] 쌍으로 저장해 segments.sort((a, b) => a[0] - b[0])로 정렬한다. 첫 구간으로 현재 범위를 시작하고, 분리된 구간을 만나거나 순회가 끝날 때 그 길이를 답에 더한다.
끝점은 $\pm10^9$ 범위이고 합집합은 $[-10^9,10^9]$ 안에 있으므로 전체 길이도 $2\cdot10^9$ 이하이다. Number로 충분하다. 겹친 선분의 오른쪽 끝점은 Math.max로 갱신한다.