방송 녹화기

면접 대비

시간 제한2초메모리 제한256 MB

요약

겹치지 않게 k대 녹화기에 녹화할 수 있는 방송의 최대 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 힙
정답자: 아직 제출이 없습니다

문제

Ada와 Bertrand, Charles는 어떤 방송을 볼지를 두고 자주 다툰다. 다툼을 줄이려고 셋은 영상 녹화기를 한 대 샀다. 이 녹화기는 서로 다른 방송 $k$ 개를 동시에 녹화하고, $k$ 개의 녹화 슬롯 중 하나에서 녹화하던 방송이 끝나면 그 슬롯은 곧바로 다른 방송을 녹화할 수 있다.

셋은 하루에 방송을 몇 개까지 녹화할 수 있는지 궁금하다. 오늘 편성표와 동시에 녹화할 수 있는 방송 수가 주어질 때, 녹화기로 녹화할 수 있는 방송의 최대 개수를 구하라. 처음부터 끝까지 통째로 녹화한 방송만 센다.

입력

첫째 줄에 정수 $n$ 과 $k$ 가 주어진다 ( $1 \le k < n \le 100\,000$ ). 다음 $n$ 개 줄에는 각각 정수 $x_i$ 와 $y_i$ 가 주어지고, $i$ 번 방송이 시각 $x_i$ 에 시작해서 시각 $y_i$ 에 끝난다는 뜻이다. 따라서 $y_i = x_j$ 인 두 방송 $i$ 와 $j$ 는 같은 슬롯에서 충돌 없이 녹화할 수 있다. $0 \le x_i < y_i \le 1\,000\,000\,000$ 이다.

출력

편성표의 방송 중 녹화기로 통째로 녹화할 수 있는 방송의 최대 개수를 한 줄에 출력한다.

예제3

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