[Algorithm] Weighted Interval Scheduling

문제 상황

스케줄링을 할 때, 작업 시간이 겹치지 않으면서, 가중치의 합이 최대가 되도록 하는 것

작업 Scheduling 알고리즘 중 Greedy 방식으로 해결한 문제가 생각나는데, Greedy Scheduling 과 차이점은 Greedy 는 엄밀히 이야기하면 가중치가 1 인 작업을 스케줄링하는 것이다

본 스케줄링에서는 그리디하게 weight 를 탐색한다면 최적해가 보장되지 않는 상황이 생긴다 (가중치가 큰 작업이 소요시간이 너무 길 수 있다. 즉 모든 케이스에 대해서 확인을 해야한다)

따라서 본 알고리즘에서는 DP 를 사용해서 문제를 해결해야한다

1. 종료시간이 가장 빠른 작업순으로 정렬을 하고

순서대로 아래와 같은 작업을 수행한다

크게 선택한 작업이 스케줄에 포함될 때 와 그렇지 않을 때로 나뉜다

1. 스케줄에 포함이 된다면, 선택한 스케줄의 시작시간 이하인 가장 늦은 종료시간을 가진 작업의 dp 값을 선택하면된다

2. 스케줄에 포함되지 않는다면 직전에 선택한 작업의 값을 선택하면된다

3. 1, 2 두 값 중 최대값을 선택한다

i-1 번째 케이스는 항상 이제까지 나온 값의 최대값을 보장하기 때문에 더 종료시간이 빠른 케이스는 볼 필요가 없다

dp[i] = Max(dp[i-1], wi + dp[j])

내가 현재 선택한 작업의 시작시간보다 더 빠른 종료시간을 가진 작업을 찾을 때, n 번 탐색할 수도 있지만, 단 하나의 인덱스(j)를 찾으면 되기 때문에 binary search 로 시간을 감소할 수 있다