축제 무대 예약
실버 V의견: 0
여름 축제에서 하나의 야외 무대에 \(N\)팀이 공연 신청을 했다. 각 팀은 공연을 원하는 시작 시간과 종료 시간을 제출하였다. 무대는 한 번에 한 팀만 사용할 수 있고, 한 공연이 끝나는 시각에 다음 공연이 바로 시작할 수 있다.
무대를 사용하는 팀의 수를 최대로 하려면 몇 팀을 선택해야 하는지 구하여라. 공연 시간이 겹치지 않는 팀들만 선택할 수 있으며, 두 공연이 정확히 같은 시각에 끝나고 시작하는 것은 허용된다.
- \(1 \le N \le 100\,000\)
- \(1 \le s_i \le e_i \le 10^9\)
첫째 줄에 공연 신청 팀 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 팀의 공연 시작 시간 \(s_i\)와 종료 시간 \(e_i\)가 공백으로 구분되어 주어진다.
선택할 수 있는 팀의 최대 수를 출력한다.
4
1 3
2 5
4 7
6 8
2
공연 \([1,3]\)과 \([4,7]\)을 선택하면 겹치지 않으며 총 \(2\)개이다. \([2,5]\)를 선택하면 끝 시간 \(5\)가 늦어서 이후에 넣을 수 있는 공연이 더 줄어드는데, 끝 시간 기준 탐욕법으로 최적 \(2\)개가 구해진다.
4
1 2
2 3
3 4
4 5
4
공연은 \([1,2],[2,3],[3,4],[4,5]\)이고, 시작 시간이 이전 공연의 끝 시간 이상이면 바로 이어서 배치할 수 있다. 네 공연 모두 선택 가능하므로 답은 \(4\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
축제 무대 예약
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
축제 무대 예약