Arantium Maestum

プログラミング、囲碁、読書の話題

区間スケジューリング問題

蟻本から。

n個の作業{t_1, t_2, ..., t_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

ある時点で選択できる作業のうち、最も終了時が早い作業{t_n}とその作業を含まないその時点以降の最善リスト{T_n}があったとして、そのリストに{t_n}を加えることで{T_n}から取り除かなければいけなくなる作業の数は0か1({t_n}が終了時が一番早いので)。つまりリストに含まれる作業数は変化しないか増加するかなので、最も終了時が早い作業{t_n}を加えることはweakly dominantな戦略である。