buyoh.hateblo.jp

残念な競技プログラミング参加者

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

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

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

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

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

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

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

競プロ界隈

コード

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

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

def schedule_problem(brackets, slotsize = 1)
    bb = brackets.sort
    ans = []
    slots = [-1]*slotsize
    bb.each do |b|
        able = slots.select{|t| t < b[1] }.max
        if able
            slots[slots.index(able)] = b[0]
            ans << b
        end
    end
    return ans
end
  • 引数brackets
    • [終了時刻, 開始時刻] を要素とする配列.
  • 引数slotsize
    • 重複を許す個数
  • 出力
    • 最も多くの仕事を行う選び方の1つを出力する.

雑な解説

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

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

高速化

配列の線形探索ではなく,もっと強力なデータ構造や2分探索を用いることで,計算量のオーダーを O(NlogK) ぐらいに減らすことができる.