R02172
겹치지 않게 최대한
브론즈 II레이팅
의견: 0
설명
\(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
태그
평가 및 의견
겹치지 않게 최대한
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
겹치지 않게 최대한
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기