마감시한 작업 스케줄링 계산기

작업마다 걸리는 시간은 똑같이 1단위이고, 각 작업은 자신의 마감시한까지 끝나야 합니다. 한 시간대(슬롯)에는 작업을 하나만 할 수 있을 때, 이익의 합이 가장 큰 작업 조합을 고르는 문제입니다. edu/activity-selection(겹치지 않게 가장 많이 고르기, 이익 없음)과 달리 여기서는 개수가 아니라 이익의 합을 최대화합니다.

이익이 큰 작업부터 훑으며, 그 작업의 마감시한 이하에서 가장 늦은 빈 슬롯에 배정합니다. 늦은 슬롯부터 채워야 마감이 이른 다른 작업이 쓸 이른 슬롯을 건드리지 않습니다. 빈 슬롯이 없으면 그 작업은 포기합니다.

교환 논증으로 증명됩니다. 이익이 가장 큰 작업을 최적해가 포함하지 않는다고 가정하면, 이미 뽑힌 작업 중 하나를 이 작업으로 바꿔도 손해 볼 수 없습니다(자리가 있고 이익이 더 크므로). 그러므로 이익이 가장 큰 작업을 포함하는 최적해가 항상 존재하고, 나머지에 같은 논증을 반복하면 그리디가 최적임이 보입니다.

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