데드라인 스케줄링 — 이익을 최대로 만드는 그리디 배치

마감 기한이 정해진 여러 일이 있고, 각각을 끝내면 이익을 얻는다. 시간은 한정되어 모든 일을 할 수는 없다. 어떤 일을 골라 어떤 순서로 해야 이익의 합이 최대가 될까?

데드라인 스케줄링 문제

$N$개의 할 일 $J_1, \cdots, J_N$ 이 있다. 각각의 일은 두 값으로 이루어진다.

$$J_i = (D_i, P_i)$$

• $D_i$ : 마감 기한(deadline) — 이 시각까지 끝내야 이익을 얻는다.
• $P_i$ : 이익(profit) — 마감 안에 끝냈을 때 얻는 값. $P_i > 0$ 을 전제한다.

모든 일은 각각 1시간이 걸린다. 한 시간에 하나의 일만 할 수 있으므로, 시간 슬롯 1, 2, 3, …에 일을 하나씩 채워 넣는 셈이다. 목표는 마감을 지키며 처리한 일들의 이익 합을 최대로 만드는 것이다.

예시

할 일이 $\{(2, 2), (1, 3), (1, 1)\}$ 라고 하자.

• $(1, 3)$ 과 $(1, 1)$ 은 둘 다 마감이 1이라, 시간 1 슬롯을 두고 경쟁한다. 둘 중 하나만 할 수 있다.
• $(2, 2)$ 는 마감이 2이므로 시간 2 슬롯에 넣을 수 있다.

가장 이익이 큰 $(1, 3)$ 을 시간 1에, $(2, 2)$ 를 시간 2에 넣으면 이익은 $3 + 2 = 5$. 남은 $(1, 1)$ 은 시간 1이 이미 차서 버린다. 이 배치가 최선이다.

---

그리디 전략

먼저 문제를 단순하게 만드는 세 가지 가정을 세운다. 모두 일반성을 잃지 않는다.

가정	이유
모든 마감 기한은 $N$ 이하다	마감을 앞으로 당겨도 문제가 없고, $N$ 뒤의 일은 어차피 할 시간이 없어 의미가 없다
이익이 내림차순으로 주어진다	정렬되어 있지 않다면 정렬하면 된다. 어차피 이익이 큰 것부터 볼 것이다
최적 스케줄에서 모든 일은 마감을 지킨다	마감을 어긴 일은 이익이 0이므로, 굳이 넣을 이유가 없다

이제 선택 규칙은 이렇다.

1. 이익이 큰 일부터 차례로 본다. 나중에 작은 일이 들어와서 못 하게 되더라도 큰 손해가 아니다.
2. 일 $J_i = (D_i, P_i)$ 를 마감 전에 놓을 수 있다면, 마감 기한에 최대한 가까운 빈 자리에 넣는다. 앞쪽 자리를 비워 두어야, 마감이 임박한 일이 나중에 들어올 자리가 남는다.

위 예시에 규칙을 적용하면, 이익 순서 $(1,3) \to (2,2) \to (1,1)$ 로 본다. $(1,3)$ 은 마감 1이라 슬롯 1에, $(2,2)$ 는 마감 2라 슬롯 2에 들어간다. 마지막 $(1,1)$ 은 마감 1인데 슬롯 1이 이미 차 있어 버려진다. 결과는 이익 5로 최적과 일치한다.

직관은 그럴듯하다. 하지만 그리디 알고리즘에서 보았듯, 매 단계의 국소 최적이 전역 최적을 보장하지는 않는다. 이 전략이 정말 최적인지 증명이 필요하다.

---

정확성 증명

증명의 핵심 도구는 교환 논증(exchange argument) 이다. “우리 알고리즘의 부분 답을, 어떤 최적해로 손해 없이 맞춰 갈 수 있다”는 것을 단계마다 보인다.

불변식

알고리즘을 실행해 일들이 배치된 상태를 $A$ 라 하자. 다음을 불변식(invariant)으로 둔다.

$A$ 가 $J_i$ 까지 본 시점에, 이에 대응하는 최적해 $S$ 가 적어도 하나 존재한다. 그리고 $j \le i$ 인 모든 $j$ 에 대해,

• $J_j$ 가 $A$ 에 나타난다 $\iff$ $J_j$ 가 $S$ 에 나타난다.
• 나타난다면, $J_j$ 의 위치(시간 슬롯)도 $A$ 와 $S$ 에서 같다.

이 불변식이 마지막($i = N$)까지 유지되면, $A$ 자체가 최적해와 완전히 일치하므로 $A$ 가 최적이다.

기초

$i = 0$ 일 때는 아무 일도 배치하지 않은 상태다. $j \le 0$ 인 $j$ 가 없으므로 조건은 공허하게 참(vacuously true) 이다. 임의의 최적해를 $S$ 로 잡으면 된다.

귀납 단계

$i$ 까지 불변식이 참이라 가정하고, $J_{i+1}$ 을 처리한 뒤에도 참임을 보인다. $A_i$ 와 $S$ 는 $j \le i$ 범위에서 일치한다.

경우 1: $J_{i+1}$ 을 놓을 수 없는 경우. 마감 $D_{i+1}$ 전에 빈 자리가 없어 알고리즘이 $J_{i+1}$ 을 버린 경우다. $A_i$ 와 $S$ 는 $D_{i+1}$ 이하 구간에서 동일하므로, $S$ 에도 빈 자리가 없다. 따라서 $S$ 역시 $J_{i+1}$ 을 넣을 수 없고, 둘 다 $J_{i+1}$ 을 갖지 않아 불변식이 유지된다.

경우 2: $J_{i+1}$ 을 시간 $t$ 에 놓는 경우. 알고리즘이 $J_{i+1}$ 을 슬롯 $t$ 에 넣었다. 이번에는 $S$ 가 $J_{i+1}$ 을 이미 갖고 있는지를 먼저 나눈다. 이렇게 나누면 두 경우가 겹치지 않는다.

2-1. $S$ 가 $J_{i+1}$ 을 이미 갖고 있는 경우. $J_{i+1}$ 이 $S$ 의 슬롯 $t'$ 에 있다고 하자. $t'$ 과 $t$ 의 관계로 나뉜다.

• $t' = t$ 이면 위치가 같으므로 그대로 일치한다.
• $t' > t$ 는 불가능하다. 알고리즘이 $J_{i+1}$ 을 $t$ 에 놓았다는 것은, $t$ 와 $D_{i+1}$ 사이 슬롯이 이미 모두 차 있었다는 뜻이다. $S$ 도 그 구간이 동일하게 차 있으므로 $t' > t$ 에 $J_{i+1}$ 을 둘 수 없다.
• $t' < t$ 이면 $J_{i+1}$ 을 슬롯 $t$ 로 옮긴다. 슬롯 $t$ 가 비어 있으면 그대로 옮기고, 다른 일 $J_x$ 가 있으면 $J_{i+1}$ 과 $J_x$ 의 자리를 맞바꾼다. 어느 쪽이든 $J_x$ 는 더 앞선 슬롯으로 이동하므로 마감을 어기지 않고, 자리 이동·교환이라 $S$ 의 총 이익은 변하지 않는다. 옮긴 뒤 $S$ 는 슬롯 $t$ 에 $J_{i+1}$ 을 갖는다.

2-2. $S$ 가 $J_{i+1}$ 을 갖고 있지 않은 경우. 이제 $S$ 의 슬롯 $t$ 상태만 따지면 된다.

• $S$ 의 $t$ 가 비어 있다면, $S$ 에 $J_{i+1}$ 을 추가하기만 해도 이익이 $P_{i+1}$ 만큼 늘어난다. 전제에서 $P_{i+1} > 0$ 이므로 $S$ 가 최적이라는 가정에 모순이고, 따라서 이 경우는 일어나지 않는다.
• $S$ 의 $t$ 에 다른 일 $J_x$ 가 있다면, 먼저 $x > i+1$ 이다. 만약 $x < i+1$ 이었다면 $J_x$ 는 이미 $A_i$ 에도 같은 자리에 있었을 텐데, 그러면 알고리즘이 슬롯 $t$ 에 $J_{i+1}$ 을 넣지 못했을 것이기 때문이다. $x > i+1$ 이므로 이익은 내림차순 가정에 의해 $P_x \le P_{i+1}$. 따라서 $S$ 에서 $J_x$ 를 $J_{i+1}$ 로 바꾸면 이익이 같거나 커진다. $S$ 가 최적이므로 더 커질 수는 없어 $P_x = P_{i+1}$ 이고, 교환해도 이익이 같으니 $S$ 는 여전히 최적이며 이제 슬롯 $t$ 에 $J_{i+1}$ 을 갖는다.

모든 경우에서, $J_{i+1}$ 까지 본 상태 $A_{i+1}$ 에 일치하는 최적해 $S$ 를 만들 수 있다. 불변식은 $i+1$ 에서도 성립한다. $\blacksquare$

---

성능

같은 알고리즘도 자료 구조에 따라 속도가 크게 달라진다.

단순한 구현: $O(N^2)$

일을 이익 순으로 본 뒤, 각 일마다 마감 $D_i$ 에서 시작해 슬롯 1까지 한 칸씩 내려가며 빈 슬롯을 찾는다.

• 일이 $N$ 개.
• 일 하나당 빈 슬롯 탐색이 최악 $O(N)$.

곱하면 $O(N^2)$ 이다.

균형 트리: $O(N \log N)$

빈 슬롯 찾기를 균형 이진 트리(balanced tree) 로 가속한다.

• 사용 가능한 시간 슬롯(또는 마감 후보)을 모두 트리에 넣는다.
• 일 $J_i$ 를 볼 때마다 트리에 ”$D_i$ 이하의 값 중 가장 큰 것은?” 을 질의한다. 이때 트리 안에서 $D_i$ 의 순위를 알 수 있고, $D_i$ 이하에서 가장 큰 빈 슬롯을 $O(\log N)$ 에 찾는다.
• 그 슬롯에 일을 배치했으면 트리에서 지우고 재배열한다. 삭제·재배열도 $O(\log N)$.

일 $N$ 개 각각에 대해 $O(\log N)$ 작업을 하므로 전체 $O(N \log N)$. 정렬 비용 $O(N \log N)$ 과 합쳐도 차수는 그대로다.