구간 스케줄링 — 겹치지 않게 가장 많은 일 고르기

시작 시간과 종료 시간이 정해진 여러 일이 있다. 한 번에 하나의 일만 할 수 있고, 시간이 겹치는 두 일은 함께 할 수 없다. 가장 많은 일을 해내려면 어떤 일들을 골라야 할까?

구간 스케줄링 문제

1편에서는 마감 기한과 이익이 있는 일들을 시간 슬롯에 배치해 이익의 합을 최대로 만들었다. 이번 문제는 다르다.

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

$$J_i = (S_i, T_i)$$

• $S_i$ : 시작 시간(start) — 이 시각에 일이 시작된다.
• $T_i$ : 종료 시간(end) — 이 시각에 일이 끝난다.

1편과 달리 일들은 길이가 제각각인 구간(interval) 이고, 이익은 모두 동일하다. 한 번에 하나의 일만 할 수 있으므로, 시간이 겹치는 두 일은 함께 할 수 없다. 이익이 같으니 목표는 단순하다 — 겹치지 않게 고른 일의 개수를 최대로 만드는 것이다.

여기서 두 일이 겹친다는 것은 한쪽이 끝나기 전에 다른 쪽이 시작한다는 뜻이다. 즉 $J_a$ 와 $J_b$ 는 $S_a < T_b$ 이고 $S_b < T_a$ 일 때 겹친다.

예시

다섯 개의 일이 있다고 하자.

$$A=(1,3),\quad B=(2,5),\quad C=(4,7),\quad D=(6,8),\quad E=(8,10)$$

$A$ 와 $B$ 는 시간 $2{\sim}3$ 에서 겹치고, $C$ 와 $D$ 는 $6{\sim}7$ 에서 겹친다. 겹치지 않게 고를 수 있는 가장 큰 묶음은 $\{A, C, E\}$ 로 세 개다. $B$ 나 $D$ 를 끼우려 하면 반드시 다른 일과 충돌해, 어떻게 골라도 세 개를 넘길 수 없다.

---

Greedy 전략

선택 규칙은 한 문장이다.

1. 종료 시간이 빠른 일부터 차례로 본다.
2. 지금 보는 일이 이미 고른 일들과 겹치지 않으면 고르고, 겹치면 버린다.

왜 하필 종료 시간일까. 빨리 끝나는 일을 고를수록 뒤에 남는 시간이 많아져, 그만큼 더 많은 일을 넣을 여지가 생기기 때문이다. 시작 시간이 빠른 일이나 길이가 짧은 일을 먼저 고르는 규칙은 이 직관을 보장하지 못한다 — 시작은 일러도 한참 뒤에 끝나는 일을 고르면 뒤가 모두 막힌다.

위 예시에 규칙을 적용해 보자. 종료 시간 순서는 $A(3) \to B(5) \to C(7) \to D(8) \to E(10)$ 이다.

• $A=(1,3)$ : 처음이라 그냥 고른다.
• $B=(2,5)$ : $A$ 가 끝나는 시각 3 전인 2에 시작하므로 겹친다. 버린다.
• $C=(4,7)$ : 마지막으로 고른 $A$ 가 3에 끝났고 $C$ 는 4에 시작하니 겹치지 않는다. 고른다.
• $D=(6,8)$ : $C$ 가 7에 끝나기 전인 6에 시작하므로 겹친다. 버린다.
• $E=(8,10)$ : $C$ 가 7에 끝났고 $E$ 는 8에 시작하니 겹치지 않는다. 고른다.

결과는 $\{A, C, E\}$, 세 개로 최적과 일치한다. 직관은 그럴듯하지만, 그리디 알고리즘에서 보았듯 국소 최적이 늘 전역 최적은 아니다. 증명이 필요하다.

---

정확성 증명

1편과 같은 도구, 교환 논증(exchange argument) 을 쓴다. 먼저 큰 그림부터 잡자.

알고리즘은 일을 하나씩 보며 “고른다 / 버린다”를 결정해 나간다. 이때 우리는 “알고리즘의 지금까지 결정과 똑같이 골라도 손해 보지 않는 최적해가 항상 곁에 있다” 를 끝까지 유지한다. 알고리즘이 마지막 일까지 처리하고 나면 그 최적해는 알고리즘의 답과 완전히 같아지고, 따라서 알고리즘의 답도 최적이 된다.

직관적으로는 최적해를 알고리즘 쪽으로 한 걸음씩 끌어당기는 과정이다. 알고리즘이 어떤 일을 골랐는데 최적해엔 그게 없다면, 최적해에서 그 자리를 차지하던 일을 우리 일로 바꿔치기한다. “종료 시간이 빠른 일부터 본다”는 규칙 덕분에, 이 바꿔치기로 일의 개수가 절대 줄지 않는다 — 이게 증명의 전부다. 아래는 이걸 단계마다 꼼꼼히 확인하는 것뿐이다.

불변식 (Invariant)

일들을 종료 시간 순으로 정렬해 두고, 앞에서부터 $i$ 개를 처리한 greedy의 상태를 $A_i$ 라 하자. 매 단계 다음을 유지한다.

$A_i$ 가 지금까지 내린 채택·포기 결정과 똑같은 최적해 $S$ 가 적어도 하나 있다. 즉 $j \le i$ 인 모든 일 $J_j$ 에 대해, $A_i$ 가 $J_j$ 를 골랐는지 버렸는지가 $S$ 에서도 똑같다.

이게 마지막($i = N$)까지 유지되면, $A_N$ 과 최적해 $S$ 의 선택이 전부 같으므로 $A_N$ 도 최적이다.

시작 (Base)

$i = 0$ 이면 아직 아무 일도 처리하지 않았다. 비교할 결정이 하나도 없으니 조건은 공허하게 참(vacuously true) 이다. 아무 최적해나 $S$ 로 잡아 두면 된다.

한 걸음 (Step)

$i$ 까지 불변식이 참이라 하고, 다음 일 $J_{i+1}$ 을 처리한 뒤에도 참임을 보인다. 지금 $A_i$ 와 $S$ 는 $j \le i$ 범위에서 선택이 같다. greedy가 $J_{i+1}$ 을 버리는 경우와 고르는 경우로 나눈다.

경우 1 — greedy가 $J_{i+1}$ 을 버린다. 이미 고른 어떤 일 $J_k$($k \le i$)와 겹쳐서 버린 경우다. $J_k$ 는 $A_i$ 가 골랐고, $S$ 도 $j \le i$ 범위에선 똑같으니 $S$ 에도 $J_k$ 가 있다. $J_{i+1}$ 은 $J_k$ 와 겹치므로 $S$ 역시 $J_{i+1}$ 을 가질 수 없다. 결국 둘 다 $J_{i+1}$ 을 버려 선택이 그대로 일치하고, 불변식이 유지된다.

경우 2 — greedy가 $J_{i+1}$ 을 고른다. $S$ 가 이미 $J_{i+1}$ 을 갖고 있으면 선택이 같으니 할 일이 없다. 까다로운 건 $S$ 에 $J_{i+1}$ 이 없을 때다. 이때 $S$ 를 손해 없이 고쳐 $J_{i+1}$ 을 넣을 수 있음을 보인다. 두 단계로 나눠 보자.

① $S$ 에서 $J_{i+1}$ 과 겹치는 일은 많아야 하나다. greedy가 $J_{i+1}$ 을 골랐다는 것은, $J_{i+1}$ 이 지금까지 고른 일들(= $S$ 의 $j \le i$ 채택분)과 하나도 안 겹친다는 뜻이다. 그러니 $S$ 안에서 $J_{i+1}$ 과 겹칠 수 있는 일은 아직 안 본 일, 즉 종료 시간이 $T_{i+1}$ 보다 늦은 일뿐이다. 그런 일이 둘 있다고 해 보자. 둘 다 $J_{i+1}$ 과 겹치니 둘 다 $T_{i+1}$ 직전 순간에 진행 중이고, 그러면 그 순간 둘끼리도 겹친다. $S$ 는 겹치는 일이 없는 모음인데 모순이다. 따라서 겹치는 일은 정확히 하나, 이를 $J_x$ 라 하자. $J_x$ 는 아직 안 본 일이라 종료가 더 늦어, $T_{i+1} \le T_x$ 다.

② $S$ 에서 $J_x$ 를 빼고 $J_{i+1}$ 을 넣는다. 하나 빼고 하나 넣으니 개수는 그대로다. 남은 건 “이 교체로 새 충돌이 생기지 않는다”는 확인뿐이다. $J_x$ 말고 $S$ 에 있던 다른 일 $J_z$ 를 보자. $J_z$ 는 원래 $J_x$ 와 안 겹쳤으니, $J_x$ 의 완전히 오른쪽이거나 완전히 왼쪽에 놓여 있다.

• $J_x$ 의 오른쪽($S_z \ge T_x$): $S_z \ge T_x \ge T_{i+1}$ 이므로 $J_z$ 는 $J_{i+1}$ 이 끝난 뒤에야 시작한다. 안 겹친다.
• $J_x$ 의 왼쪽($T_z \le S_x$): $J_x$ 가 $J_{i+1}$ 과 겹쳤으니 $S_x < T_{i+1}$, 따라서 $T_z \le S_x < T_{i+1}$ — $J_z$ 는 $J_{i+1}$ 보다 먼저 끝난다. 그러면 종료 시간 순에서 $J_z$ 는 $J_{i+1}$ 보다 앞서 처리된 일($j \le i$)이고, $S$ 에 있으니 $A_i$ 도 골랐던 일이다. 그런데 greedy는 이미 고른 일들과 안 겹치는 걸 확인하고서 $J_{i+1}$ 을 골랐다. 그러니 $J_z$ 도 $J_{i+1}$ 과 안 겹친다.

어느 쪽이든 충돌이 없다. 교체한 $S$ 는 개수를 유지한 채 여전히 최적이고, 이제 $J_{i+1}$ 을 갖는다. 불변식은 $i+1$ 에서도 성립한다.

---