スポンサーリンク

1235. Maximum Profit in Job Scheduling

daily challengeで出てきて難しかったので備忘録。

Maximum Profit in Job Scheduling - LeetCode
Maximum Profit in Job Scheduling - We have n jobs, where every job is scheduled to be done from startTime to endTime, obtaining a profit of profit. You're give...

n個のjobのstartTime, endTime, profitが与えられ、スケジュールが重複しないように利益を最大化する問題。

全探索を考えた時、jobを選ぶ / 選ばないの2通りをn回繰り返すので、O(2^N)となり間に合わない。

ここで、全探索で得られるパターンを何個か眺めてみると以下のルールが使えそうなことに気づく。

1.あるjobを行う場合、次に行うjobの候補は実行中のjobのendTime以降

2.ある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を実行しない場合、1つ次の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)となる。



 

コメント

タイトルとURLをコピーしました