[일반] 가중치가 있는 강의실 배정 문제?

[익명(125.251)]

https://www.acmicpc.net/problem/11000

Baekjoon Online Judge

이 문제 풀다가 궁금해져서 그러는데 

만약 강의마다 가중치가 있으면 어떻게 푸나요?

이거처럼 끝나는 시간 기준으로 정렬해서 푸는 건 안될 거 같은데

관련 자료나 문제가 있나요??

[익명(1.210)]

그리디하게 풀 수 있으려나 이건 궁금하네

[익명(118.235)]

각 강의가 [si, ei]고 가중치 wi일때 안 겹치게 가중치 최대화 이거 말하는거면 일단 좌표압축하고 dp[i] = (시점 i에 끝나는 강의를 마지막으로 배치했을 때 최대 가중치 합)이라고 정의하면 dp 전이가 prefix 최댓값 구하면 빠르게 되는 형태라서 세그먼트 트리나 펜윅 쓰면 nlogn에 풀림

[익명(121.130)]

https://www.acmicpc.net/problem/19623