算法练习 Leetcode 力扣 1203. Sort Items by Groups Respecting Dependencies 解法

feellikelearning June 22, 2020 0 Comments

这题还是挺难写对的。经过几番尝试以后，发现最好理解的算法就是先对group做一次拓扑排序。然后按group的顺序，对每个group里的items的做拓扑排序。这题增加另一难点在于gorup是-1的情况。其实相当于每个-1都是自己的新group。于是大量的工作其实在建立group的dependency graph上。拓扑排序的函数可以写一次反复重用。Python解法如下：

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

        cur_group = m + 1
        for i in range(len(group)):
            if group[i] == -1:
                group[i] = cur_group
                cur_group += 1

        group_ids = set(group)

        itemLevelBeforeGroups = []
        for i in range(len(beforeItems)):
            each_node_before_groups = [group[before] for before in beforeItems[i]]
            each_node_before_groups = list(filter(lambda x: x != i, each_node_before_groups))
            itemLevelBeforeGroups.append(each_node_before_groups)

        # beforeGroups
        beforeGroups = {g: set() for g in group}
        for i in range(len(itemLevelBeforeGroups)):
            beforeGroups[group[i]].update(itemLevelBeforeGroups[i])
            beforeGroups[group[i]] = beforeGroups[group[i]].difference([group[i]])
        # print(f'beforeGroups = {beforeGroups}')

        groupToItems = {g: [] for g in group}
        for i in range(len(group)):
            groupToItems[group[i]].append(i)
        # print(f'group to items: {groupToItems}')

        cache = {}
        group_order = []
        itemLevelBeforeGroups

        def dfs(start, cache, order, before_nodes):
            # print(f'start =  {start}')
            if start in cache:
                return cache[start]
            cache[start] = False
            for before in before_nodes[start]:
                # print(f'  before = {before}')
                if not dfs(before, cache, order, before_nodes):
                    # print('found loop!')
                    return False
            # print('  {before} done')
            cache[start] = True
            order.append(start)
            return True

        for g in group_ids:
            if not dfs(g, cache, group_order, beforeGroups):
                return []
        # print(f"group_order = {group_order}")

        item_order = []
        item_cache = {}
        for g in group_order:
            for node in groupToItems[g]:
                if not dfs(node, item_cache, item_order, beforeItems):
                    return []

        # print(f"item order = {item_order}")
        return item_order

本题是复合题，三个点：
1. 拓扑排序本身，然后分别用在group level和每个group的item level
2. 建立group dependency
3. handle group == -1的情况，就是给每个这种item assign新group