演算法練習 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