레이팅 미적용농부 존은 소들이 휴식을 취하고 더 많은 우유를 생산하는 데 도움이 될 것이라 생각하여 소들을 위한 수영장을 열었다.
안전을 위해 그는 \(N\)마리의 소를 안전 요원으로 고용했는데, 각 소는 하루 중 어떤 연속된 시간 구간을 담당하는 근무 시간을 가진다. 편의상 수영장은 매일 시각 \(0\)부터 시각 \(10^9\)까지 열려 있으므로, 각 근무는 소가 근무를 시작하는 시각과 끝내는 시각을 나타내는 두 정수로 표현할 수 있다. 예를 들어 시각 \(t = 4\)에 시작해 시각 \(t = 7\)에 끝나는 안전 요원은 세 단위의 시간을 담당한다(양 끝점은 시간상의 "점"임에 유의하라).
안타깝게도 농부 존은 자금으로 감당할 수 있는 것보다 \(K\)명 더 많은 안전 요원을 고용했다. 정확히 \(K\)명의 안전 요원을 해고해야 할 때, 남은 안전 요원들의 근무로 여전히 담당될 수 있는 시간의 최대 길이는 얼마인가? 어떤 시간 구간은 적어도 한 명의 안전 요원이 있으면 담당된 것으로 본다.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)과 \(K\)가 주어진다 (\(K \leq N \leq 100,000, 1 \leq K \leq 100\)). 다음 \(N\)개의 줄에는 각 안전 요원의 근무 시작 시각과 끝 시각을 나타내는 \(0 \ldots 10^9\) 범위의 정수 두 개가 주어진다. 이러한 끝점들은 모두 서로 다르다. 서로 다른 안전 요원의 근무는 겹칠 수 있다.
농부 존이 \(K\)명의 안전 요원을 해고했을 때 여전히 담당될 수 있는 시간의 최대 길이를 나타내는 수 하나를 출력한다.
lifeguards.in · 출력을 쓸 파일 lifeguards.out3 2
1 8
7 15
2 1412In this example, FJ should fire the lifeguards covering \(1 \ldots 8\) and
\(7 \ldots 15\).
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > January > Platinum