23.03.09 Today’s Leetcode

210. Course Schedule II (medium)

indegree : # of prerequisities

DFS Approach

class Solution:
    def findOrder(self, N, P):
        G, indegree, ans = defaultdict(list), [0]*N, []
        for nxt, pre in P:
            G[pre].append(nxt)
            indegree[nxt] += 1
        
        def dfs(cur):
            ans.append(cur)
            indegree[cur] = -1
            for nextCourse in G[cur]:
                indegree[nextCourse] -= 1
                if indegree[nextCourse] == 0: 
                    dfs(nextCourse)            
        for i in range(N):
            if indegree[i] == 0:
                dfs(i)

        return ans if len(ans) == N else []

BFS Approach

class Solution:
    def findOrder(self, N, P):
        G, indegree, q, ans = defaultdict(list), [0]*N, deque(), []
        for nxt, pre in P:
            G[pre].append(nxt)
            indegree[nxt] += 1
        
        for i in range(N):
            if indegree[i] == 0:
                q.append(i)
        while q:
            cur = q.popleft()
            ans.append(cur)
            for nextCourse in G[cur]:
                indegree[nextCourse] -= 1
                if indegree[nextCourse] == 0: 
                    q.append(nextCourse)
                    
        return ans if len(ans) == N else []

630. Course Schedule III (hard)

DFS Approach

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        n = len(courses)
        taken = [False] * n
        res = -1
        
        def dfs(cur, count):
            nonlocal res
            res = max(res, count)
            for index, (dur, last) in enumerate(courses):
                if taken[index]: continue
                time = cur + dur
                if time <= last:
                    taken[index] = True
                    dfs(time, count + 1)
                    taken[index] = False
        
        dfs(0, 0)
        return res

Greedy Approach

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        prefix = 0 
        pq = [] # max-heap 
        for x, y in sorted(courses, key=lambda x: x[1]): 
            prefix += x
            heappush(pq, -x)
            while prefix > y: prefix += heappop(pq)
        return len(pq)