로그인 후 문제풀이가 가능합니다.

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

1 ≤ N ≤ 10⁶ 인 정수
1 ≤ S_i ＜ F_i ≤ 10⁹

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