区間スケジューリング問題
蟻本から。
n個の作業がある。
各作業は開始時と終了時が決まっており、同時に二つの作業をすることはできない。
作業をどう選べば、完了した作業数を最大化できるか。
かなり有名な貪欲法の問題。ポイントは、開始時や長さではなく、終了時を基準に選んでいくこと。
def solve(tasks): tasks = sorted(tasks, key=lambda x:x[1]) res = [] cur_time = -1 for task in tasks: if task[0] > cur_time: res.append(task) cur_time = task[1] return res
ある時点で選択できる作業のうち、最も終了時が早い作業とその作業を含まないその時点以降の最善リストがあったとして、そのリストにを加えることでから取り除かなければいけなくなる作業の数は0か1(が終了時が一番早いので)。つまりリストに含まれる作業数は変化しないか増加するかなので、最も終了時が早い作業を加えることはweakly dominantな戦略である。