도시 정전 구간
골드 V의견: 0
스마트 시티 '리세'의 전력망 관리자는 오늘 하루 총 \(N\)건의 정전 구간 기록을 받았다. \(i\)번째 기록은 시각 \(L_i\)부터 시각 \(R_i\)까지 어느 구역에 정전이 발생했음을 의미하며, 같은 시각에 여러 구역의 정전이 겹칠 수 있다.
관리자는 '실제로 어떤 구역이든 정전이 진행 중이었던 시간의 총 길이'를 보고서에 기재해야 한다. 이 값을 구하여라.
구간 \([L_i, R_i]\)는 닫힌 구간이 아니라 반열린 구간 \([L_i,\, R_i)\)로 해석한다: 시각 \(L_i\) 포함, 시각 \(R_i\)는 포함하지 않는다.
- \(1 \le N \le 200\,000\)
- \(-10^9 \le L_i < R_i \le 10^9\)
- 정수 좌표이다.
첫째 줄에 정전 기록의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 정전 구간 \(L_i\)와 \(R_i\)가 공백으로 구분되어 주어진다.
정전이 진행 중이었던 시간의 총 길이를 한 줄에 출력한다.
3
1 5
3 8
10 12
9
\([1,5]\)과 \([3,8]\)은 겹쳐서 \([1,8]\)로 합쳐지고, \([10,12]\)는 분리되어 있다. 총 정전 길이는 \((8-1)+(12-10)=9\)이다.
3
2 6
6 9
1 3
8
\([1,3]\), \([2,6]\), \([6,9]\)를 정렬하면 \([1,3]\), \([2,6]\), \([6,9]\)가 되어 \([1,9]\)로 합쳐진다. 총 길이 \(8\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
도시 정전 구간
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
도시 정전 구간