LeetCode 1203. 项目管理

约 7 分钟
文章信息 2 个分类 4 个标签
分类
LeetCode 困难
标签
深度优先搜索 广度优先搜索 图 拓扑排序

题目描述

✅ 1203. 项目管理

题意分析

给所有项目排出一个执行顺序。beforeItems[v] 中的每个项目都必须先于 v 出现，同时属于同一组的项目必须在结果中连续地放在一起。

每个项目恰好出现一次，满足要求的顺序可以不唯一；无法同时满足依赖与组连续性时返回空数组。group[i] = -1 表示项目没有指定组，不代表所有这样的项目原本就属于同一个组。

解法：项目与组分别拓扑排序，再按组拼接

核心思路

[!blue]

普通项目依赖只约束谁先谁后，同组连续还要求把整个组当作一个连续块安排。因此需要同时决定“组块的先后”和“每个组内部项目的先后”，用两张有向图分别描述这两个层面。

先为每个无组项目单独分配一个新组，这样它作为单独一块参与排序，不会额外限制其他无组项目必须和它挨在一起。代码复制组数组后再补编号，保留调用方原来的分组数据。

对每条依赖 u → v，项目图都记录这条边。若它们不同组，还要在组图中加入 group[u] → group[v]：两组各自必须连续，一旦存在从前一组到后一组的依赖，整个前一组就必须排在后一组之前。组内依赖则不创建组边，避免产生无意义的组自环。

分别做两次拓扑排序。项目图有环时，基本先后关系就无法满足；组图有环时，虽然某些具体项目也许没有成环，组块之间却必须互相排在对方之前，连续性要求仍然无解。因此两张图都要成功输出全部节点。

获得项目拓扑序后，按顺序把项目放入各自组的桶中，保留同组项目在该序列中的相对位置。最后按组拓扑序依次连接每个桶，就自然让同组项目连续出现。

这次重新拼接不会破坏依赖：同组边的两个端点仍保持项目拓扑序里的顺序；跨组边由组拓扑序保证整块前后关系。每个项目只进入一个桶、每个桶只输出一次，所以全部项目也恰好出现一次。

解题步骤

  1. 复制 group，给每个 -1 项目分配独立新编号，并得到最终组数。
  2. 按 beforeItems 建立前置项目到后置项目的边及项目入度；跨组依赖再同步加入组图和组入度。
  3. 两张图分别执行拓扑排序，若任一输出数不足对应节点数，返回空数组。
  4. 依项目拓扑序把项目追加到对应组桶中，保留桶内顺序。
  5. 依组拓扑序逐桶连接，得到满足项目依赖和组连续性的结果。

代码实现

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        group = group.clone();

        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = m++;
            }
        }

        List<List<Integer>> items = new ArrayList<>();
        List<List<Integer>> groups = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            items.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            groups.add(new ArrayList<>());
        }

        int[] itemDegree = new int[n];
        int[] groupDegree = new int[m];

        for (int v = 0; v < n; v++) {
            for (int u : beforeItems.get(v)) {
                items.get(u).add(v);
                itemDegree[v]++;

                if (group[u] != group[v]) {
                    groups.get(group[u]).add(group[v]);
                    groupDegree[group[v]]++;
                }
            }
        }

        List<Integer> itemOrder = topo(items, itemDegree);
        List<Integer> groupOrder = topo(groups, groupDegree);

        if (itemOrder.size() != n || groupOrder.size() != m) {
            return new int[0];
        }

        List<List<Integer>> buckets = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            buckets.add(new ArrayList<>());
        }

        for (int item : itemOrder) {
            buckets.get(group[item]).add(item);
        }

        int[] answer = new int[n];
        int index = 0;

        for (int g : groupOrder) {
            for (int item : buckets.get(g)) {
                answer[index++] = item;
            }
        }

        return answer;
    }

    private List<Integer> topo(List<List<Integer>> graph, int[] degree) {
        List<Integer> order = new ArrayList<>();

        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                order.add(i);
            }
        }

        for (int head = 0; head < order.size(); head++) {
            for (int v : graph.get(order.get(head))) {
                if (--degree[v] == 0) {
                    order.add(v);
                }
            }
        }

        return order;
    }
}

func sortItems(n, m int, group []int, beforeItems [][]int) []int {
    group = append([]int(nil), group...)
    for i := range group {
        if group[i] == -1 {
            group[i] = m
            m++
        }
    }
    items, groups := make([][]int, n), make([][]int, m)
    itemDegree, groupDegree := make([]int, n), make([]int, m)
    for v, previous := range beforeItems {
        for _, u := range previous {
            items[u] = append(items[u], v)
            itemDegree[v]++
            if group[u] != group[v] {
                groups[group[u]] = append(groups[group[u]], group[v])
                groupDegree[group[v]]++
            }
        }
    }
    topo := func(graph [][]int, degree []int) []int {
        order := []int{}
        for i, d := range degree {
            if d == 0 {
                order = append(order, i)
            }
        }
        for head := 0; head < len(order); head++ {
            for _, v := range graph[order[head]] {
                degree[v]--
                if degree[v] == 0 {
                    order = append(order, v)
                }
            }
        }
        return order
    }
    itemOrder, groupOrder := topo(items, itemDegree), topo(groups, groupDegree)
    if len(itemOrder) != n || len(groupOrder) != m {
        return []int{}
    }
    buckets := make([][]int, m)
    for _, item := range itemOrder {
        g := group[item]
        buckets[g] = append(buckets[g], item)
    }
    answer := make([]int, 0, n)
    for _, g := range groupOrder {
        answer = append(answer, buckets[g]...)
    }
    return answer
}

复杂度分析

设项目数为 n，补齐无组项目后的组数为 g，项目依赖总数为 E。

  • 时间复杂度：$O(n+g+E)$，建立两张图、两次拓扑排序和按组拼接都是线性处理；组边数量不超过项目依赖数量。
  • 空间复杂度：$O(n+g+E)$，保存组编号副本、图、入度、拓扑结果及分组桶。

代码允许多个项目依赖产生重复的组边，每记录一次边也相应增加一次入度，删除时逐条减少，两处数量一致即可正确工作。

关键点总结

[!green]

  • 项目层解决依赖顺序，组层解决连续块顺序，两种约束缺一不可。
  • 按项目序装桶保留组内依赖，按组序输出保证跨组依赖，拼接后两类边都合法。
  • 无组项目各自独立成组，空组可以出现在组拓扑序中，但不会向答案追加任何项目。
  • 拓扑函数用结果列表兼作队列，入度归零时追加，读取游标向后推进即可。

易错点总结

[!yellow]

  • 把全部 -1 项目合并为同一组，会额外引入它们必须连续的条件，可能制造原本没有的无解情况。
  • 只做项目拓扑排序，结果可能让同组项目散落在其他组之间。
  • 只检查项目图是否有环，会漏掉组块先后关系的循环矛盾。
  • 同组依赖也加入组图，会形成组指向自己的边，错误地阻止该组入度归零。
  • 组边只在邻接表去重却仍重复增加入度，或反过来只在入度侧去重，会导致计数无法正确解除。
  • 装桶时不保留项目拓扑序，可能在同一个组内重新颠倒已经满足的依赖。

相似题目

题目 难度 关联与区别
210. 课程表 II 中等 在普通项目拓扑排序上增加组级依赖，单独的一次课程表排序不能保证同组连续。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/43667379
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！