Участник:Evgin/parallel courses ii

Материал из DISCOPAL
< Участник:Evgin
Версия от 22:37, 26 декабря 2020; Evgin (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/parallel-courses-ii/ Python3 <code-python> class Solution: def minNumberOfSemesters(self, n: int, dependencies: List[List[int]…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/parallel-courses-ii/

Python3

class Solution:
    def minNumberOfSemesters(self, n: int, dependencies: List[List[int]], k: int) -> int:
        from itertools import combinations
        from functools import reduce
        from operator import or_
 
        if k == 1:
            return n
        req = n * [0]
        for a, b in dependencies:
            req[b - 1] |= (1 << (a - 1))
        S = [0]
        done = (1 << n) - 1
        for c in range(1, n + 1):
            T = set()
            for s in S:
                ready = [(1 << i) for i in range(n) if (req[i] == (s & ((1 << i) | req[i])))]
                for r in combinations(ready, min(k, len(ready))):
                    t = s | reduce(or_, r)
                    T.add(t)
            if done in T:
                return c
            S = T