레이팅 미적용설명
\(N\)개의 강연이 있고, \(i\)번째 강연은 시각 \(s_i\)에 시작해서 시각 \(e_i\)에 끝난다. 한 강의실에서 이 강연들 중 서로 시간이 겹치지 않도록 최대한 많이 진행하려 한다.
한 강연이 끝나는 시각과 다른 강연이 시작하는 시각이 같은 것은 겹치는 것으로 보지 않는다. 겹치지 않게 고를 수 있는 강연 수의 최댓값을 출력하여라.
제약
\(1 \le N \le 1000\), \(0 \le s_i < e_i \le 10^9\)
입력 형식
첫째 줄에 강연의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 강연의 시작 시각 \(s_i\)와 끝 시각 \(e_i\)가 공백으로 구분되어 주어진다.
출력 형식
겹치지 않게 진행할 수 있는 강연 수의 최댓값을 한 줄에 출력한다.
예제 1
입력
4
1 3
2 5
4 7
6 8
출력
2
설명
\([1,3)\), \([4,7)\)을 고르면 서로 겹치지 않아 최대 \(2\)개를 고를 수 있다.
예제 2
입력
3
0 10
0 10
0 10
출력
1
설명
세 구간이 모두 겹치므로 하나만 고를 수 있어 답은 \(1\)이다.
문제 정보
riseoj 작성
출처 Original
태그