#1203

Sort Items by Groups Respecting Dependencies

expert · 1085 · lc hard +32 · verified · 65.6% accepted · 1,906 likes · top 70%

Description

You have n items, each optionally belonging to one of m groups. group[i] == -1 means item i belongs to no group. Both items and groups use 0-based indexing.

Produce an ordering of all items such that:

- Items in the same group appear consecutively.

- For each item i, all items in beforeItems[i] appear earlier in the result.

Return any valid ordering, or an empty list if none exists.

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.

Code

1

2

3

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

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