daily challengeで出てきて難しかったので備忘録。
n個のjobのstartTime, endTime, profitが与えられ、スケジュールが重複しないように利益を最大化する問題。
全探索を考えた時、jobを選ぶ / 選ばないの2通りをn回繰り返すので、O(2^N)となり間に合わない。
ここで、全探索で得られるパターンを何個か眺めてみると以下のルールが使えそうなことに気づく。
１．あるjobを行う場合、次に行うjobの候補は実行中のjobのendTime以降
２．あるjobを行わない場合、次に行うjobの候補はstartTimeが近いjob
あるjobを行ったかどうかで以降のjobが分岐していくため、グラフを構築することができ、再起で解けそうになる。
まずは前処理として、開始時間が早い順にjobを並び替える。
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
n = len(profit)
jobs = []
for s, e, p in zip(startTime, endTime, profit):
jobs.append((s,e,p))
jobs.sort()次に再起を実装する。
現在のjobを実行する場合、endTimeより後のstartTimeのjobを探索する。
現在のjobを実行しない場合、１つ次のstartTimeのjobを実行する。
job = nまで探索したら0を返して修了。
def rec(job):
if job == n:
return 0
next_job = n
for i, (s, e, _) in enumerate(jobs):
if s >= jobs[job][1]:
next_job = i
break
maxProfit = max(rec(job+1), jobs[job][2] + rec(next_job))
return maxProfit次のjobを探索するループ部分はO(N)となり遅い。
startTime順にjobを前処理しているので、二分探索が使えそう。
next_job = bisect.bisect_left(jobs, jobs[job][1], key=lambda x:x[0])また、一度計算した要素は次の計算にも流用出来るのでメモ化も行う。
@lru_cache(maxsize=None)
def rec(job):以上を繋げて提出。
from functools import lru_cache
import bisect
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
n = len(profit)
jobs = []
for s, e, p in zip(startTime, endTime, profit):
jobs.append((s,e,p))
jobs.sort()
@lru_cache(maxsize=None)
def rec(job):
if job == n:
return 0
next_job = bisect.bisect_left(jobs, jobs[job][1], key=lambda x:x[0])
maxProfit = max(rec(job+1), jobs[job][2] + rec(next_job))
return maxProfit
return rec(0)
時間計算量は、
最初にstartTime順に配列を用意してソートするのにO(N logN)
max(rec(job+1), jobs[job][2] + rec(next_job))の所で2回ずつ再起が呼び出されるのでO(2N)
次のjobを決める二分探索がO(logN)なので、再起そのものはO(2N logN) = O(N logN)となる。
全体を通してみると、前処理 O(N logN) + 再起 O(N logN) = O(N logN)となる。
空間計算量は、
startTime, endTime, profitを格納する配列が O(3N)
再起のスタックが O(2N)
メモがO(N)
トータルで O(N)となる。
コメント