가중 구간 스케줄링 계산기

개수가 아니라 가중치(수익) 합을 최대로 한다는 점이 다릅니다. 활동 선택 문제(edu/activity-selection)는 모든 구간의 가치가 같다고 보고 끝나는 시각이 이른 것부터 고르는 탐욕이 항상 최적이지만, 구간마다 가중치가 다르면 그 탐욕은 더 이상 최적이 아니어서 동적계획법이 필요합니다.

구간을 끝나는 시각 순으로 정렬해 1..n 번을 매기고, p(j)를 «j와 겹치지 않는(끝이 j의 시작보다 이르거나 같은) 구간 중 번호가 가장 큰 것»으로 둡니다. OPT(j) = max(OPT(j−1), 가중치(j) + OPT(p(j)))로, j를 버렸을 때와 담았을 때 중 큰 쪽을 택합니다. p(j)는 정렬된 끝 시각 배열에서 이분 탐색으로 찾아 전체를 O(n log n)에 풉니다.

가중치가 섞이면 최적이 아닙니다. 짧은 구간 여럿을 모아도 값어치가 큰 구간 하나에 못 미칠 수 있기 때문입니다. 예를 들어 [0,2]/1 [1,3]/1 [2,4]/1을 이어 붙이면 2를 고를 수 있지만, 이 셋을 모두 덮는 [0,4]/100 하나를 고르면 100입니다.

이것도 최적이 아닙니다. 값어치가 크다고 넓은 구간을 먼저 담으면 그 안에 들어가는 작은 구간 여럿의 합이 더 컸을 기회를 잃습니다. [0,10]/10 하나를 먼저 담으면 그 안의 [0,3]/6 [3,6]/6 [6,10]/6을 모두 잃어 10에 머물지만, 이 셋을 담으면 18입니다. 0/1 배낭에서 비율 탐욕이 최적이 아닌 것과 같은 이유입니다.

j번째 구간을 담을지 버릴지는 «j 하나의 값어치 + 그 앞에서 가능한 최선»과 «j를 무시한 j−1까지의 최선» 중 큰 쪽으로 결정되고, 이 부분 문제들의 최적해를 그대로 이어 붙이면 전체 최적해가 됩니다(최적 부분구조). 작은 사례에서는 2ⁿ 개의 모든 부분집합을 완전탐색해 같은 값이 나오는지로 검증할 수 있습니다.

겹치지 않은 것으로 봅니다. 10시에 끝나는 작업과 10시에 시작하는 작업은 이어서 할 수 있습니다. p(j)를 찾을 때도 «끝 ≤ 시작(j)»을 기준으로 합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.