개발자 크루

Hit Lightening

5일의 전사

Hit Lightening

썸네일

강의실 배정

난이도
3 단계
참가자
0
제출
0
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 5초 256MB
C 1초 256MB
C++ 1초 256MB
Java 5초 256MB
Python 5초 256MB

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

제약조건

1 ≤ N ≤ 106 인 정수
1 ≤ Si < Fi ≤ 109

입력형식

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다.

출력형식

첫 번째 줄에 최대 강의 수를 출력하라.

입력예제1

3 1 3 2 4 3 5

출력예제1

2