Festival Scheduling
골드 III의견: 0
당신의 축제에는 메인 무대가 하나뿐이다. \(N\)개의 공연 후보가 있으며, \(i\)번째 공연은 반열린 시간 구간 \([s_i, e_i)\)를 원하고 그 대가로 \(p_i\)의 이익을 가져다준다. 두 공연의 구간이 겹치지 않는 한 두 공연을 모두 일정에 넣을 수 있다. 한 공연이 끝나는 순간 다른 공연이 시작하는 경우(\(e_i = s_j\))는 괜찮다.
서로 겹치지 않는 공연들의 부분집합을 골라 총 이익을 최대화하여라.
- \(1 \le N \le 200000\)
- \(0 \le s_i < e_i \le 10^9\)
- \(1 \le p_i \le 10^9\)
총 이익이 32비트를 넘을 수 있으므로 64비트 산술을 사용해야 한다.
첫째 줄에는 정수 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 각각 세 정수 \(s_i\ e_i\ p_i\)가 주어진다.
얻을 수 있는 최대 총 이익을 정수 하나로 출력한다.
3
1 3 50
2 5 20
4 6 70120Pick act 1 ([1,3), 50) and act 3 ([4,6), 70). They don't overlap and earn 50 + 70 = 120. Act 2 overlaps act 1, and taking it instead would earn less.
3
1 4 10
2 5 10
3 6 1010All three intervals pairwise overlap, so at most one act can run; any single act earns 10.
riseoj 작성
출처 Original
평가 및 의견
Festival Scheduling
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Festival Scheduling