안전 요원

농부 존은 소들이 휴식을 취하고 우유를 더 많이 생산하는 데 도움이 되리라 생각하여, 소들을 위한 수영장을 열었다.

안전을 위해 그는 \(N\)마리의 소를 안전 요원으로 고용했으며, 각 소는 하루 중 어떤 연속된 시간 구간 동안 근무한다. 편의상 수영장은 매일 시각 \(t=0\)부터 시각 \(t = 1,000,000,000\)까지 열려 있으므로, 각 근무는 소가 근무를 시작하는 시각과 끝내는 시각을 나타내는 두 정수로 표현할 수 있다. 예를 들어, 시각 \(t = 4\)에 시작해서 시각 \(t = 7\)에 끝나는 안전 요원은 세 단위의 시간을 담당한다 (양 끝점은 시간상의 "점"이라는 것에 유의한다).

안타깝게도 농부 존은 자금으로 감당할 수 있는 것보다 안전 요원을 1마리 더 고용해 버렸다. 정확히 한 명의 안전 요원을 해고해야 할 때, 남은 안전 요원들의 근무로 여전히 커버할 수 있는 시간의 최대량은 얼마인가? 어떤 시간 구간은 적어도 한 명의 안전 요원이 있으면 커버된다.

Problem credits: Brian Dean

Problem credits: Brian Dean

입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 100,000\))이 주어진다. 다음 \(N\)개의 줄에 각 안전 요원의 근무 시작점과 끝점을 나타내는 \(0 \ldots 1,000,000,000\) 범위의 두 정수가 주어진다. 이러한 모든 끝점은 서로 다르다. 서로 다른 안전 요원의 근무 시간은 겹칠 수 있다.

농부 존이 안전 요원 1마리를 해고했을 때 여전히 커버할 수 있는 시간의 최대량을 나타내는 수 하나를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > January > Silver