문제
농부 창호는 요즈음 대유행중인 무서운 소로나 바이러스(COWVID-19) 때문에 고민이 많다.
농부 창호는 소들의 오후 일과를 위해, 일직선 좌표계로 표현되는 목장에 각 N마리의 소들을 배치시키려고 한다.
목장 내에는 [s,e]로 표현되는 M개의 구간이 있으며, 이 구간 내에 있는 풀은 잘 자라서 먹을 수 있다.
농부 창호는 모든 소들을 이 구간 내에 배치시키되, 사회적 거리두기를 위해 소들간의 거리를 최대화시키고자 한다.
구체적으로는, 두 소 사이의 거리의 최솟값이 D라고 하면, D를 최대화시키려고 한다.
이 D를 구하는 프로그램을 작성하라.
(소들은 무조건 정수 좌표 위에 배치되며, 구간 [s,e]에서 각 경계 좌표인 s와 e에도 소들이 위치할 수 있다.)
입력
첫 줄에 정수 N과 M이 주어진다. (2≤N≤100,000, 1≤M≤100,000)
다음 M줄에 걸쳐서, 소들이 먹을 수 있는 풀이 있는 구간인 s, e가 공백을 사이에 두고 주어진다.
각 좌표는 0이상
그 어떤 두 구간도 겹치거나 맞닿지 않는다.
출력
D의 최댓값을 첫 줄에 출력한다. D>0인 답이 나올 수 있는 입력예시가 항상 보장된다.
예제1
입력
53
02
47
99
출력
2
D=2를 만족시키는 한 가지 방법은 소들을 각각 x = 0, 2, 4, 6, 9에 배치하는 것이다.
출처
USACO 2020 US Open Silver