활동 선택 문제 계산기

끝나는 시각이 이른 것부터 고르면 됩니다. 남은 활동 중 끝이 가장 이른 것을 고르고, 그것과 겹치는 것을 버리고, 다시 되풀이합니다. 이 방식이 최대 개수를 낸다는 것이 증명되어 있습니다.

교환 논증으로 증명합니다. 어떤 최적해가 있다고 할 때 그 첫 활동을 «끝이 가장 이른 활동»으로 바꿔치기해도 뒤에 오는 활동들과 여전히 겹치지 않습니다. 끝이 더 이르거나 같기 때문입니다. 개수가 그대로이므로 끝이 가장 이른 것을 포함하는 최적해가 반드시 존재하고, 나머지에 같은 논증을 되풀이하면 됩니다.

최적이 아닙니다. 짧지만 두 활동의 경계에 걸친 것 하나가 양쪽을 동시에 죽일 수 있습니다. [0,5] [4,6] [5,10]에서 가장 짧은 [4,6]을 먼저 고르면 1개밖에 못 고르지만, 끝 기준으로 고르면 [0,5]와 [5,10] 2개를 고릅니다.

길이가 긴 활동 하나가 짧은 여럿을 통째로 막기 때문입니다. [0,10] [1,2] [3,4]에서 시작이 가장 이른 [0,10]을 고르면 나머지가 모두 겹쳐 1개로 끝나지만, 끝 기준으로는 [1,2]와 [3,4] 2개를 고릅니다.

그것은 다른 문제입니다. 모두 배정하되 방 수를 최소로 하는 문제의 답은 «한 시점에 동시에 겹치는 최대 개수»입니다. 이 계산기도 함께 내 주며, 겹치는 최대 개수만큼 방을 두면 모든 활동을 배정할 수 있습니다.

겹치지 않은 것으로 봅니다. 10시에 끝나는 회의와 10시에 시작하는 회의는 이어서 할 수 있습니다. 이동이나 정리 시간이 필요하다면 끝 시각에 그만큼을 더해서 넣으면 됩니다.

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