청소 근무 배정

면접 대비

시간 제한1초메모리 제한128 MB

요약

1번부터 T번까지의 교대를 가장 적은 수의 구간으로 덮어야 한다. 각 구간은 연속한 교대를 담당하며, 최소 구간 수를 출력하고 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 구간, 투 포인터
정답자: 아직 제출이 없습니다

문제

농부 John은 축사 청소를 위해 자신의 소 $N$ 마리( $1 \le N \le 25{,}000$ ) 중 일부를 배정하려 한다. 그는 항상 정확히 한 마리 이상의 소가 청소를 하고 있기를 원하며, 하루를 $T$ 개의 근무 시간대(shift, $1 \le T \le 1{,}000{,}000$ )로 나누었다. 시간대는 첫 번째가 $1$ 번, 마지막이 $T$ 번이다.

각 소는 하루 중 어떤 한 구간 동안에만 청소 작업을 할 수 있다. 청소에 배정된 소는 자신의 구간 전체 동안 일한다.

농부 John을 도와, (i) 모든 시간대가 최소 한 마리의 소로 덮이고 (ii) 참여하는 소의 수가 최소가 되도록 소를 시간대에 배정하라. 모든 시간대를 덮는 것이 불가능하면 $-1$ 을 출력한다.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $T$ .
둘째 줄부터 $N+1$ 번째 줄까지: 각 줄에 한 소가 일할 수 있는 구간의 시작 시각과 끝 시각이 주어진다. 소는 시작 시각의 시간대부터 끝 시각의 시간대까지(양 끝 포함) 일한다.

출력

첫째 줄: 농부 John이 필요로 하는 소의 최소 수. 모든 시간대를 덮을 수 없으면 $-1$ .

예제4

예제 1
입력
```
3 10
1 7
3 6
6 10
```
예상 출력
```
2
```
예제 2
입력
```
1 5
1 5
```
예상 출력
```
1
```
예제 3
입력
```
3 6
1 2
3 4
5 6
```
예상 출력
```
3
```
예제 4
입력
```
1 1
1 1
```
예상 출력
```
1
```