Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
有一系列课程,每个课程有一些先修课,修每门课需要时间time[i],问最少多长时间能修完所有课,拓扑排序

 1 #2050
 2 
 3 #Runtime: 1240 ms (Beats 72.73%)
 4 #Memory: 43.6 MB (Beats 31.82%)
 5 
 6 class Solution(object):
 7     def minimumTime(self, n, relations, time):
 8         """
 9         :type n: int
10         :type relations: List[List[int]]
11         :type time: List[int]
12         :rtype: int
13         """
14         adj = defaultdict(list)
15         ind = [0] * n
16         time_cost = [0] * n
17         for x, y in relations:
18             adj[x - 1].append(y - 1)
19             ind[y - 1] += 1
20         q = deque([])
21         for x in range(n):
22             if ind[x] == 0:
23                 q.append(x)
24                 time_cost[x] = time[x]
25         while len(q):
26             x = q.popleft()
27             for y in adj[x]:
28                 time_cost[y] = max(time_cost[x] + time[y], time_cost[y])
29                 ind[y] -= 1
30                 if ind[y] == 0:
31                     q.append(y)
32         return max(time_cost)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理