[알고리즘] Greedy Algorithm - Interval Scheduling

Interval scheduling

•  Job j starts 𝑠𝑗 and finishes at 𝑓 𝑗.
• Two jobs are compatible if they don’t overlap
• Goal: find maximum subset of mutually compatible jobs

일을 가장 많이 사용하는 방법을 찾는 경우를 찾는다고 했을 때 문제입니다.

직관적으로 봤을 때 b, e, h를 고를 시 가장 많은 경우의 수를 고려하지만 직관적으로 해결 하는 것이 아닌 다양한 접근법을 이용해서 해결 해보겠습니다.

문제 예시

Approach 1) Earliest start time: Consider jobs in ascending order of 𝑠 𝑗

일이 시작되는 시간 중에서 가장 먼저 시작되는 일을 기준으로 시작한다.

 

Approach 1) 반례

위 경우에서 가장 먼저 시작되는 s1를 기준으로 시작하게 되면 나머지 일들을 하나도 못 고르게 된다. 그러므로 최적의 해로 볼 수 없습니다.

 

Approach 2) Shortest interval: Consider jobs in ascending order of 𝑓 𝑗− 𝑠 𝑗

가장 짧은 일만 먼저 선택을 한다.

 

Approach 2) 반례

이 문제에서 s1를 선택할 경우 s2, s3를 못고르게 된다. 그러므로 반례가 있으므로 최적의 해로 볼 수 없습니다.

 

Approach 3) Fewest conflicts: Consider jobs in that have the fewest conflicts first

위 그림처럼 적게 충돌하는 일을 우선적으로 선택하면서 나아가는 방법이다.

 

Approach 3) 반례

위 그림은 s1, s2, s3, s4가 최적의 해이지만 많이 충돌한다는 이유로 선택하지 못하게 된다. 그러므로 이 풀이도 최적의 해가 될 수 없습니다.

 

Approach 4) Earliest finish time: Consider jobs in ascending order of 𝑓 𝑗

가장 빨리 끝나는 일을 먼저 고르는 방법을 취하는게 최적의 해가 된다는 사실을 알 수 있습니다.

나머지 접근법 1, 2, 3에 대입을 하더라도 최적의 해가 나오게 됩니다.

---

문제

백준 1931번: 회의실 배정

이 문제는 위의 알고리즘을 사용해볼 수 있는 문제입니다!

https://www.acmicpc.net/problem/1931