시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 24 12 12 63.158%

문제

사람 N명이 회의를 하려고 한다. i번째 사람은 회의실에 Si시간부터 Ei시간까지 머무른다. 두 사람이 동시에 회의실에 머무르는 순간이 존재한다면, 두 사람이 같이 회의를 하게 할 수 있다. 한 사람은 최대 한 회의에만 포함될 수 있다. 최대한 많은 회의를 열어 작업 효율성을 높이려 한다. 이 때 열 수 있는 회의의 개수를 구하여라.

입력

첫 줄에 N이 주어진다. (1 ≤ N ≤ 5 × 105)

N개의 줄 동안 Si와 Ei가 공백으로 구분되어 주어진다. (모든 i에 대해서, 1 ≤ Si ≤ Ei ≤ 109)

출력

최대로 열 수 있는 회의의 개수를 출력한다.

예제 입력 1

5
1 5
2 4
3 3
5 6
999999999 1000000000

예제 출력 1

2

예제 입력 2

3
1 1
2 2
1 2

예제 출력 2

1

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 1 G번