시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 124 35 28 31.461%

문제

X축 위에 여러 개의 짧은 선들이 흩어져 있다. 이 선들은 [Li, Ri]로 나타내는데 이는 선이 Li에서 시작해 Ri에서 끝남을 의미한다. 우리는 이들 중 적은 수의 선들만을 이용해서 [0, M]을 완전히 덮어 버리고 싶다. 최소 개수의 선들을 이용하여 [0, M]을 덮어버리는 프로그램을 작성하시오.

입력

각 테스트 케이스는 M(1≤M≤50,000) 과 "Li Ri"(|Li|, |Ri|≤50,000, i≤100,000)쌍으로 구성이 된다. 각각은 다른 행으로 분리되어 있다. 입력은 "0 0"으로 끝난다.

출력

[0, M]을 덮는데 필요한 선의 개수를 출력한다. 만약 선을 덮는 방법이 존재하지 않으면 “0”을 출력하면 된다.

예제 입력

1
-1 0
0 1
0 0

예제 출력

1

힌트

출처

  • 잘못된 조건을 찾은 사람: yukariko