Greedy - Deadline Scheduling / Tape Storage

Deadline Scheduling

경우 1 : 최대 이익이 되게 하라

• Job(Deadline, Profit)
• Job 서로 겹치기 불가능
• Profit에 의해 내림차순 정렬

---

알고리즘

1. 데드라인 안쪽의 비어 있는 자리 중 가장 뒤쪽에 넣는다.

---

정확성 증명

Base)
n = 0 일 때 넣을 Job이 없다.

Step)
n = i 일 때 알고리즘이 만들어 낸 답 A 가 있고 잠정적인 답 S가 있다고 가정한다.
현재까지 스케줄링되어 있는 J1, J2, … , Ji 은 A와 S가 일치한다.

n = i + 1 일 때
만약 A 가 Ji+1을 스케줄링하지 않았다면 Ji+1의 데드라인 안쪽에서 넣을 빈자리가 없다는 의미이다.
따라서 S 역시 데드라인 안쪽에 넣을 빈자리가 없게 되므로 A와 S는 일치한다.

만약 A 가 Ji+1을 t 자리에 넣었을 때

1) 만약 S 가 Ji+1을 선택하지 않았고 t 자리가 비어 있다면
당연히 Ji+1을 t 자리에 넣는 것이 이익이 최대가 되므로 t 자리가 비어 있는 경우는 존재하지 않는다.

2) 만약 S 가 Ji+1을 선택하지 않았고 t 자리에 Jx가 들어가 있다면 x > i+1이다.
따라서 이익에 따라 내림차순 정렬 되어있는 Job 이기 때문에 Ji+1 ≥ Jx 가 된다.
이때 Ji+1 > Jx 라면 S는 답이 될 수 없기 때문에 Ji+1 = Jx이다.
이 경우엔 S에서 Jx를 Ji+1로 교체하더라도 문제없으므로 A와 S 두 가지 모두 가능한 답이다.

3) 만약 S가 Ji+1을 선택했으나 t’ 자리에 존재한다면
만약 t = t’이라면 문제없다.
만약 t < t’이라면 데드라인 안쪽 중 가장 뒤쪽인 t 보다 t’이 더 뒤쪽이라는 의미인데 이것은 불가능하다.
만약 t > t’이라면 둘 다 데드라인 안쪽이므로 t 자리와 t’을 서로 교환해서 바꾸더라도 최종 이익이 변하지 않는다.
그러므로 이 역시 A와 S 모두 가능한 답이다.

따라서 알고리즘은 모든 경우에 대하여 성립한다.

시간 복잡도)
평범하게 만들면 O(n^2)
AVL Tree 같은 Balanced Tree를 사용한다면 O(nlogn)

AVL Tree의 정점은 데드라인(Di)
1. 추가하는 Ji의 Di를 AVL Tree에 root에서부터 검사했을 시
Di 보다 작거나 같은 값 중 가장 큰 값을 선택한다. (데드라인 안쪽 중 가장 뒤쪽)
2. 선택된 정점은 제거된다.

 

---

경우 2 : 최대한 많은 Job을 선택하라

• Job(starttime, endtime)
• Job 서로 겹치기 불가능
• 이익은 모든 Job이 동일

---

알고리즘

1. Job은 endtime 기준으로 오름차순 정렬한다.
2. 차례대로 스케줄링한다.

---

정확성 증명

Base)
n = 0 일 때 스케줄링 할 Job 이 없다.

Step)
n = i 일 때 알고리즘이 만들어낸 답 A 가 있고 잠정적인 답 S가 있다고 하자.
J1, J2, … , Ji 가 스케줄링 되어 있으며 이것은 A와 S가 일치한다.

n = i+1 일 때 A가 Ji+1을 선택하지 않았다면 Ji+1과 겹치는 Job이 존재하기 때문에 넣지 못한 것이다.
S는 A와 일치하기 때문에 역시 겹치는 Job 이 발생하여 넣지 못한다. 따라서 A와 S가 일치한다.

만약 A 가 Ji+1을 선택했고 S 도 Ji+1을 선택했다면 문제없다.
그러나 S가 Ji+1을 선택하지 않았다면 S와 A가 일치하는 부분을 제외하고
나머지 S에 저장된 Job 들 중 가장 endtime 이 빠른 Jx와 Ji+1을 교체한다.
Jx 앞의 구간이 어떻게 길든 그 구간 안에는 Job 이 올 수 없다.
왜냐하면 그 구간에 Job이 온다면 자동으로 그것이야말로 Jx 이기 때문이다.
그러므로 Ji+1과 Jx를 교체한다면 여전히 A와 S는 같은 최대 이익을 얻을 수 있다.

따라서 알고리즘은 모든 경우에 대하여 성립한다.

 

---

11000번: 강의실 배정

이 문제는 위 알고리즘에서 좀 더 생각을 해야 풀 수 있어요!

---

Tape Storage

• Data(Length, Frequency)
• 길이가 짧고 빈도수가 높은 순서대로 채워 나가야 한다.
• Storage의 맨 앞부터 읽기 시작한다.

---

알고리즘

1. 데이터는 F/L로 내림차순 정렬한다.
2. 순서대로 넣는다.

---

정확성 증명

Data들이 F/L 을 기준으로 내림차순 정렬되어 있을 때
n까지의 기대 값을 다음과 같이 계산할 수 있다.

S = F1L1 + F2(L1 + L2) + … + Fi(L1 + … + Li) + Fi+1(L1 + … + Li+1) + … + Fn(L1 + … + Ln)

만약 Fi/Li < Fi+1/Li+1이라고 가정하면 n까지의 기대 값을 다음과 같이 계산할 수 있다.

A = F1L1 + F2(L1 + L2) + … + Fi+1(L1 + … + Li-1 + Li+1) + Fi(L1 + … + Li-1 + Li+1 + Li) + … + Fn(L1 + … + Ln)

S - A = Fi+1Li - FiLi+1 = LiLi+1(Fi+1/Li+1 - Fi/Li)인데
이때 Fi+1/Li+1 > Fi/Li라고 가정했기 때문에 S-A > 0, S>A 가 된다.

S의 기댓값이 더 크므로 알고리즘은 정확하다.