선분 덮기
시간 제한2초메모리 제한128 MB
최대 10만 개의 선분이 주어질 때 구간 [0, M]을 완전히 덮는 데 필요한 최소 선분 개수를 구하고, 불가능하면 0을 출력합니다.
문제
X축 위에 여러 선분이 주어집니다. 각 선분은 [L_i, R_i]로 표시하며, (L_i)에서 시작해 (R_i)에서 끝납니다. 이 선분들 중 일부를 골라 구간 [0, M] 전체를 덮으려고 합니다. 구간 [0, M]을 완전히 덮는 데 필요한 선분의 최소 개수를 구하세요.
입력
첫 줄에 정수 (M)((1 \le M \le 50,000))이 주어집니다. 이어지는 각 줄에는 한 선분을 나타내는 두 정수 (L_i)와 (R_i)((|L_i|, |R_i| \le 50,000))가 주어집니다. 선분 목록은 0 0이 입력되면 끝납니다. 선분의 개수는 최대 100,000개입니다.
출력
구간 [0, M]을 완전히 덮는 데 필요한 선분의 최소 개수를 출력합니다. 덮을 수 없다면 0을 출력합니다.