1203. Sort Items by Groups Respecting Dependencies

题目信息

题号:

1203

难度:

Hard

主题:

拓扑排序、分组依赖、图

原题:

LeetCode 1203

重点:

每个物品必须位于所有前置物品之后,同时同组物品在结果中必须连续;未分组物品可视为各自独立的新组

题目重述

有 n 个物品,编号为 0 到 n - 1,以及 m 个已有分组。group[i] 表示物品 i 所属组;值为 -1 的物品尚未分组。beforeItems[i] 列出必须排在物品 i 之前的物品。

请返回包含全部物品的一种排列,使每项依赖都得到满足,并且属于同一组的所有物品在排列中形成一个连续区间。可以为每个未分组物品分配独立的新组。若不存在合法排列,返回空数组;若答案不唯一,可返回任意一种。

1 <= m <= n <= 3 * 10^4,group.length == beforeItems.length == n;group[i] 为 -1 或已有组编号,依赖下标均合法。

自建示例

跨组依赖与组内依赖可以同时满足:

输入:n = 4, m = 2, group = [0,0,1,1], beforeItems = [[],[0],[1],[2]]
输出:[0,1,2,3]
解释:0 必须先于 1,1 先于 2,2 先于 3;两个组也分别保持连续。

依赖形成环时没有合法顺序:

输入:n = 3, m = 1, group = [0,0,0], beforeItems = [[2],[0],[1]]
输出:[]
解释:依赖要求 2 在 0 前、0 在 1 前、1 又在 2 前,形成有向环。