회의실 예약
하루에 회의를 최대한 많이 배정하려면 일찍 시작하는 순서가 아니라 일찍 끝나는 순서로 수락해야 한다. 종료가 빠를수록 남는 시간이 길어지고, 이 전략은 최적임이 증명되어 있다.
구간 스케줄링에서 탐욕 전략별 선택 과정과 결과 비교.
작업 구간을 편집하며 Earliest-Finish, Start, Shortest 세 정렬 전략의 선택 결과를 비교해, 탐욕이 최적인 경우와 실패하는 반례를 직접 만들어 확인합니다.
탐욕 구간 스케줄링은 task를 어떤 순서로 정렬하느냐에 따라 결과가 달라진다. Earliest-Finish 전략만이 항상 최대 개수를 선택한다는 것이 수학적으로 증명되어 있다. Start나 Shortest 전략으로 바꾸면 탐욕이 실패하는 반례를 직접 볼 수 있다.
시간복잡도 O(n log n)
sort by end; keep task if start >= last_end
하루에 회의를 최대한 많이 배정하려면 일찍 시작하는 순서가 아니라 일찍 끝나는 순서로 수락해야 한다. 종료가 빠를수록 남는 시간이 길어지고, 이 전략은 최적임이 증명되어 있다.
zip의 허프만 코딩, OS의 SJF 스케줄링, 다익스트라가 모두 그리디다. 다만 성립 조건을 벗어나면 조용히 틀린다. shortest 전략은 그럴듯해 보이지만 최적을 놓치는 예다.
최적해의 첫 선택을 그리디의 첫 선택으로 바꿔도 손해가 없음을 보이면, 귀납적으로 그리디 전체가 최적임이 증명된다. start 전략에서는 이 논증이 성립하지 않아 반례가 바로 나온다.