회의실 배정
면접 대비시간 제한2초메모리 제한128 MB
시작 시간과 종료 시간이 주어진 N개의 회의 중 서로 겹치지 않게 최대한 많이 선택하는 고전적인 그리디 구간 스케줄링 문제입니다.
문제
회의실이 하나 있다. 이 회의실을 사용하려는 (N)개의 회의가 주어질 때, 서로 시간이 겹치지 않도록 회의실을 배정해서 진행할 수 있는 회의의 최대 개수를 구하라.
각 회의는 시작 시간과 끝나는 시간이 주어진다. 회의가 한 번 시작되면 중간에 중단할 수 없다. 한 회의가 끝나는 시각과 동시에 다음 회의가 시작되는 것은 가능하다. 시작 시간과 끝나는 시간이 같은 회의도 있을 수 있으며, 이 경우 시작하자마자 끝나는 회의로 본다.
입력
첫째 줄에 회의의 수 (N)이 주어진다. (1 \le N \le 100{,}000)
둘째 줄부터 (N)개의 줄에는 각 회의의 시작 시간과 끝나는 시간이 공백으로 구분되어 주어진다. 시작 시간과 끝나는 시간은 (0) 이상 (2^{31}-1) 이하의 정수이다.
출력
회의실을 사용할 수 있는 회의의 최대 개수를 첫째 줄에 출력한다.
힌트
((1,4), (5,7), (8,11), (12,14)) 회의를 선택할 수 있다.