Kの重複を許す区間スケジューリング問題

2018/02/22 更新 文章を修正

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

http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用．

区間スケジューリングは次の問題である．仕事が n 個与えられる．各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定されている．仕事は開始時刻から終了時刻まで続けて行わなければならず，同時に複数の仕事を行うことはできない．最も多くの仕事を行う方法を求めよ．

Kの重複を許す区間スケジューリング問題

区間スケジューリング問題では，『同時に複数の仕事を行うことはできない』としていた． これを『K個までは同時に複数の仕事が出来る』と置き換えてみる．

すなわち，上の区間スケジューリング問題はK=1の重複を許す区間スケジューリング問題である．

問題集

• CodeSprint で K=2 が出題されている(リンクを探せず)．
  • CodeSprint Japan 40pt : 区間の選択 - komiyamの日記
• yukicoder No.580 旅館の予約計画 - yukicoder
  • 入力が面倒だが，scanfや正規表現で読み取って，day*1440+hour*60+min でおｋ
  • 問題の制約上 O(NM) で accept 出来る．

コード

先にコードを貼ります．Ruby．計算量はO(NK)．

#211486 (Ruby) No.580 旅館の予約計画 - yukicoder

def schedule_problem(brackets, slotsize = 1)
    
    brackets = brackets.sort
    
    ans = []
    slots = [-1]*slotsize
    
    brackets.each do |b|
        end_time, begin_time = b
        
        able = slots.select{|t| t < begin_time }.max
        
        if able
            slots[slots.index(able)] = end_time
            ans << b
        end
    end
    
    return ans
end

• 引数brackets
  • [終了時刻, 開始時刻] を要素とする配列．
• 引数slotsize
  • 重複を許す個数
• 出力
  • 最も多くの仕事を行う選び方の1つを出力する．

雑な解説

K=1の区間スケジューリング問題の解き方を知っている前提で書いていきます．

• 『最も終了時刻の早い仕事を行う最適解が存在する』ことが分かっているので，最も終了時刻の早い仕事から順に調べていけば良い．
  • 2行目 sort の部分に該当．
• 今，ある仕事b=[end_time,begin_time]について調べていて，K個のスロットのうち，いくつかの仕事がbegin_timeまでに終わっているとする．
  • selectの部分に該当．
• 終わっている仕事のうち，終了時刻が最も遅い仕事と置き換えるのが最適である．
  • maxで最も遅い終了時刻を取得する．

高速化

もっと強力なデータ構造や2分探索を用いることで，計算量のオーダーを O(NlogK) に減らすことができる．

• 例えば，C++11のmultisetと二分探索を用いる方法がある．
  • cielさんの記事が分かりやすい． http://cielavenir.github.io/blog/2017/10/23/inn-reservation/