강의실 배정

면접 대비

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

요약

N개 수업의 시작과 종료 시각이 주어질 때 겹치는 수업이 같은 교실을 쓰지 않도록 필요한 최소 교실 수를 구합니다.

문제

수업 $N$ 개의 시간표가 주어진다. $i$ 번째 수업은 시각 $S_i$ 에 시작해서 시각 $T_i$ 에 끝난다. 모든 수업을 진행하려면 강의실이 최소 몇 개 필요한지 구하라.

한 강의실에서는 같은 시각에 수업을 하나만 진행한다. 앞 수업이 끝난 시각에 다음 수업을 바로 시작할 수 있으므로, $T_i \le S_j$ 이면 수업 $i$ 와 수업 $j$ 를 같은 강의실에 배정할 수 있다.

첫째 줄에 수업의 개수 $N$ 이 주어진다. ( $1 \le N \le 2 \times 10^5$ )

다음 $N$ 개의 줄에 각각 $S_i$ 와 $T_i$ 가 공백으로 구분되어 주어진다. ( $0 \le S_i < T_i \le 10^9$ )

모든 수업을 진행하는 데 필요한 강의실의 최소 개수를 첫째 줄에 출력한다.