회의
면접 대비시간 제한1초메모리 제한1024 MB
각 사람이 [Si, Ei] 구간에 회의실에 머무를 때, 구간이 겹치는 두 사람을 짝지어 최대한 많은 회의 쌍을 만든다.
문제
사람 N명이 회의를 하려고 한다. i번째 사람은 회의실에 Si시간부터 Ei시간까지 머무른다. 두 사람이 동시에 회의실에 머무르는 순간이 존재한다면, 두 사람이 같이 회의를 하게 할 수 있다. 한 사람은 최대 한 회의에만 포함될 수 있다. 최대한 많은 회의를 열어 작업 효율성을 높이려 한다. 이 때 열 수 있는 회의의 개수를 구하여라.
입력
첫 줄에 N이 주어진다. (1 ≤ N ≤ 5 × 105)
N개의 줄 동안 Si와 Ei가 공백으로 구분되어 주어진다. (모든 i에 대해서, 1 ≤ Si ≤ Ei ≤ 109)
출력
최대로 열 수 있는 회의의 개수를 출력한다.