시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB129234424024.793%

문제

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
-1 0
0 1
0 0

예제 출력 1

1

예제 입력 2

1
-1 0
-5 -3
2 5
0 0

예제 출력 2

0

출처

  • 데이터를 추가한 사람: alperatz
  • 잘못된 조건을 찾은 사람: yukariko