Weighted Interval Scheduling

구간끼리 겹치지 않게 하는 가중치 스케줄링 문제

1. Interval Scheduling

• 구간과 구간의 시작, 끝 시간이 주어졌을 때

  1) 구간끼리 겹치지 않으면서

  2) 가장 많은 구간을 선택하려면

• 그리디 방법으로 최적해를 구한다.

2. Weighted Interval Scheduling

• 구간과 구간의 시작, 끝 시간, 각 구간의 가중치가 주어졌을 때

  1) 구간끼리 겹치지 않으면서

  2) 가중치의 합이 가장 크게하는 구간의 집합을 구하려면

• 그리디로는 최적해를 보장하지 못한다 (가중치가 큰거부터 선택함)

• 동적계획법을 통해 최적해를 구한다

3. 동적계획법 Weighted Interval Scheduling

• n개 구간들을 종료 시간에 의해 정렬한다. (구간 = I1, I2, ... I,n 구간 Ii의 시작/끝 시간 = si, fi, 가중치 = wi)

• 가중치가 가장 큰 interval scheduling은 w[i]를 포함하거나 미포함했을 때 구간들 중 더 큰 경우이다

OPT(i) = max{OPT(i-1), w[i] + OPT(j)}
// j = I[i]와 겹치지 않으며 종료 시간이 가장 늦은 구간

알고리즘

1. 구간을 종료 시간 기준으로 정렬한다
2. 구간 시작 전에 끝나는 구간을 찾아 배열 P에 담는다
3. 배열 P를 이용해 각 구간까지 최대 가중치를 구한다

시간복잡도 : O(n log n)