Skip to main content

630. Course Schedule III

https://leetcode.com/problems/course-schedule-iii/

Python​

Top-Down DP (Timelimit Exceed)​

  • Time: O(N*D) # N = len(courses); D = deepth
  • Space: O(N*D)
from functools import cache


class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda course: course[1])

        @cache
        def dp(i: int, current: int):
            if i == len(courses):
                return 0
            duration, end = courses[i]

            pick_cost = 0
            if (now := current + duration) <= end:
                pick_cost = 1 + dp(i+1, now)

            ignore_cost = dp(i+1, current)

            return max(pick_cost, ignore_cost)

        return dp(0, 0)

Bottom-Up DP with Max Heap​

import heapq


class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda course: (course[1], course[0]))

        dp = []
        current = 0
        for duration, end in courses:
            current += duration
            heapq.heappush(dp, -duration)  # Max Heap

            if current > end:
                current += heapq.heappop(dp)

        return len(dp)