What pattern does this problem follow?

This problem follows the graph indegree plus topological ordering pattern, applied to both items and groups with dependency constraints.

How do I handle items without groups?

Assign a unique temporary group ID to each ungrouped item to ensure all items are included in the group-level topological sort.

What if there is no valid ordering?

Detect cycles in the item or group dependency graphs; if a cycle exists, return an empty list as no valid solution is possible.

Can multiple valid outputs exist?

Yes, multiple topological orderings may satisfy all dependencies; any valid ordering can be returned according to the problem requirements.

How do DFS and BFS apply here?

DFS can be used to detect cycles and produce a topological sort recursively, while BFS with indegree tracking produces a valid ordering iteratively for both items and groups.

#1203

Hard

auto_awesome图·搜索

LeetCode 题解工作台

项目管理

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。 group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1 。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。请你帮忙按要求安排这些…

深度优先搜索广度优先搜索图拓扑排序

题目描述

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。
项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]

示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

提示：

1 <= m <= n <= 3 * 10⁴
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] 不含重复元素

lightbulb

解题思路

方法一：拓扑排序

我们先遍历数组 $group$ ，对于每个项目，如果其不属于任何小组，则将其新建一个小组，编号为 $m$ ，并将 $m$ 的值加一。这样我们就能保证所有项目都属于某个小组了。然后，我们用一个数组 $groupItems$ 记录每个小组包含的项目，数组下标为小组编号，数组值为包含的项目列表。

接下来，我们需要建图。对于每个项目，我们需要建立两种图，一种是项目间的图，一种是小组间的图。我们遍历数组 $group$ ，对于当前项目 $i$ ，它所在的小组为 $group[i]$ ，我们遍历 $beforeItems[i]$ ，对于其中的每个项目 $j$ ，如果 $group[i] = group[j]$ ，说明 $i$ 和 $j$ 属于同一小组，我们在项目图中添加一条 $j \to i$ 的边，否则说明 $i$ 和 $j$ 属于不同的小组，我们在小组间的图中添加一条 $group[j] \to group[i]$ 的边，并且更新对应的入度数组。

接下来，我们先对小组间的图进行拓扑排序，得到排序后的小组列表 $groupOrder$ ，如果排序后的列表长度不等于小组总数，说明无法完成排序，返回空列表。否则，我们遍历 $groupOrder$ ，对于其中的每个小组 $gi$ ，我们将该小组包含的项目列表 $groupItems[gi]$ 进行拓扑排序，得到排序后的项目列表 $itemOrder$ ，如果排序后的列表长度不等于该小组包含的项目总数，说明无法完成排序，返回空列表。否则，我们将 $itemOrder$ 中的项目加入答案数组中，最终返回该答案数组即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是项目总数和小组总数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

class Solution:
    def sortItems(
        self, n: int, m: int, group: List[int], beforeItems: List[List[int]]
    ) -> List[int]:
        def topo_sort(degree, graph, items):
            q = deque(i for _, i in enumerate(items) if degree[i] == 0)
            res = []
            while q:
                i = q.popleft()
                res.append(i)
                for j in graph[i]:
                    degree[j] -= 1
                    if degree[j] == 0:
                        q.append(j)
            return res if len(res) == len(items) else []

        idx = m
        group_items = [[] for _ in range(n + m)]
        for i, g in enumerate(group):
            if g == -1:
                group[i] = idx
                idx += 1
            group_items[group[i]].append(i)

        item_degree = [0] * n
        group_degree = [0] * (n + m)
        item_graph = [[] for _ in range(n)]
        group_graph = [[] for _ in range(n + m)]
        for i, gi in enumerate(group):
            for j in beforeItems[i]:
                gj = group[j]
                if gi == gj:
                    item_degree[i] += 1
                    item_graph[j].append(i)
                else:
                    group_degree[gi] += 1
                    group_graph[gj].append(gi)

        group_order = topo_sort(group_degree, group_graph, range(n + m))
        if not group_order:
            return []
        ans = []
        for gi in group_order:
            items = group_items[gi]
            item_order = topo_sort(item_degree, item_graph, items)
            if len(items) != len(item_order):
                return []
            ans.extend(item_order)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m + total dependencies) because we traverse each node and edge in both item and group graphs once. Space complexity is O(n + m + total dependencies) to store adjacency lists, indegrees, and temporary ordering arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate identifies the need for dual-level topological sorting.
question_mark
Candidate correctly assigns unique groups to ungrouped items to prevent cross-group ambiguity.
question_mark
Candidate accounts for cycles in item or group dependencies.

warning

常见陷阱

外企场景

error
Failing to assign unique group IDs to items with group[i] == -1 causing invalid cross-group sorting.
error
Mishandling cycles in dependencies, leading to incorrect output instead of an empty list.
error
Processing items before group-level dependencies are resolved, breaking the relative ordering pattern.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing items to belong to multiple groups and handling overlapping dependencies.
arrow_right_alt
Changing the problem to return the lexicographically smallest valid ordering instead of any valid ordering.
arrow_right_alt
Introducing weighted dependencies where some items must precede others based on priority instead of just presence.

help

常见问题

外企场景

继续练习

#1462 课程表 IV #802 找到最终的安全状态 #329 矩阵中的最长递增路径