Interval Scheduling, Interval Partitioning, Huffman Encoding, Set Cover

매번 현재 상황에서 최선의 선택을 한다. 우선순위 큐로 구현되는 것을 기억하자

Interval Scheduling Problem

Jobs: start at $s_j$, ends at $f_j$

Compatible: don’t overlap

Goal: find a maximum subset of mutually compatible jobs

ex. 아래처럼 4개를 선택하면 된다.

Greedy Template: 어떤것을 Greedy의 기준으로 삼을 것인가? 즉 priority queue에서의 key를 뭘로 할것인가?

• Earliest start time

  

  위같은 반례가 존재한다.

• Earliest finish time (OPTIMAL)

• shortest interval

  

  위같은 반례가 존재한다.

• fewest conflicts

  

  위같은 반례가 존재한다.

Proof of [Finish time] greedy algorithm

귀류) assume not optimal

우선 finish time 기준 greedy로 job들을 $i_1, i_2, …, i_k$로 뽑았다고 하자 (뭔지 모르지만) Optimal한 순서가 있을 텐데, 위 순서와 처음부터 $j_1, j_2, …, j_r$까지 겹치고 그 뒤로는 다르다고 해보자. (물론 r=0일 수도 있다)