시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1292 | 344 | 240 | 24.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 0 0 1 0 0
1
1 -1 0 -5 -3 2 5 0 0
0