動機

Hard題都是來看創意的

把 group encode成起點與終點

同時這題也是遇過最複雜的一題

Problem

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

  • The items that belong to the same group are next to each other in the sorted list.
  • There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).

Return any solution if there is more than one solution and return an empty list if there is no solution.

 

Example 1:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]Output: [6,3,4,1,5,2,0,7]

Example 2:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]Output: []Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.

 

Constraints:

  • 1 <= m <= n <= 3 * 104
  • group.length == beforeItems.length == n
  • -1 <= group[i] <= m - 1
  • 0 <= beforeItems[i].length <= n - 1
  • 0 <= beforeItems[i][j] <= n - 1
  • i != beforeItems[i][j]
  • beforeItems[i] does not contain duplicates elements.

Sol

n+ group_idx是group的起點 n++m group_idx是group的終點

接著從終點開始走回去(因為是dfs)，所以從數字大的(group的終點)走回去

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        prog = defaultdict(int) # 1 process, 2 done
        gh = defaultdict(set)
        not_used = set(range(n))
        
        # add group
        for (i,g) in enumerate(group):
            if g != -1:
                gh[n+g].add(i) # entry of group
                gh[i].add(n+m+g) # exit of group
            
        # add before relation
        for (i,bs) in enumerate(beforeItems):
            for b in bs:
                if group[i] == group[b] and group[i] != -1:
                    gh[b].add(i)
                else:
                    i_entry = n+group[i] if group[i] != -1 else i
                    b_exit = n+m+group[b] if group[b] != -1 else b
                    gh[b_exit].add(i_entry)

        def topo(i,ret):
            if prog[i] == 1:
                raise 'loop'
            elif prog[i] == 2:
                return []
            else:
                prog[i] = 1
                [topo(x,ret) for x in gh[i]]
                if i<n:
                    not_used.remove(i)
                    ret.append(i)
                prog[i] = 2
                return ret
        
        try:
            order = sorted(gh.keys())[::-1]
            dep = []
            [topo(i,dep) for i in order]
            return dep[::-1]+list(not_used)
        except:
            return []