인터벌 스케줄링 (Interval Scheduling)

Greedy Algoritm (그리디 알고리즘) 의 첫 번째 예시라고 할 수 있는 문제가

바로 이 인터벌 스케줄링 문제이다

 

백준사이트 1931번 문제가 바로 그 문제이다 (https://www.acmicpc.net/problem/1931)

 

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

위와 같이 11가지의 시작하는 시간, 끝나는 시간이 주어질 때,

어떻게 하면 가장 "많은" 일을 할 수 있을까 하는 문제이다

 

1. 일의 시간이 가장 짧은 순서대로 ? (Shortest interval)

시간이 가장 짧은 일이,

맨 뒤의 일이라면 비효율적이게 된다

 

2. 시작시간이 빠른 순서대로 ? (Earliest start time)

시작시간이 가장 빠른 일이,

가장 늦게 끝나면 비효율적이게 된다

 

3. 겹치는 일이 가장 적은 순서대로 ? (Fewest conflicts)

이 역시 쉽게 반례를 들 수 있다

 

그렇다면, 하나의 정렬만으로는 이 사건을 해결할 수 없는 것일까?

아니다

 

4. 끝나는 시간이 빠른 순서대로 (Earliest Finish Time)

이와 같은 방법이면, 반례를 찾을 수 없다

또한 러닝타임은 sorting하는 데에 O(nlogn)이고 카운팅 하는 데에 O(n)이므로

O(nlogn)의 러닝타임을 갖는다 

 

그러나 여기에 가중치(weight)을 생각하게 되면 또 다른 문제가 된다는 것을 알 수 있다!