buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

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 が出題されている(リンクを探せず).
  • yukicoder No.580 旅館の予約計画 - yukicoder
    • 入力が面倒だが,scanf正規表現で読み取って,day*1440+hour*60+min でおk
    • 問題の制約上 O(NM) で accept 出来る.

コード

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

#211486 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) に減らすことができる.