作业问题:找到作业序列的最小数量

Question

我有N不同的作业。有些工作可以连续完成。

需要安排连续作业以形成作业序列，使得作业序列M的数量最小。

问题的形式是最大基数匹配。

但是，当最大基数匹配时，作业序列的数量肯定是最小的吗？

我正在寻找一种算法来解决它。

示例

N=6

可以执行以下作业：

作业1可以转到作业2、5。

然后作业2可以转到作业3。

作业4可以转到作业2、5。

作业5可以转到作业6。

执行作业分配时，我们得到以下2个作业序列：

1-2-3

4-5-6

则M＝2。

这可以被视为找到所有航班(工作)的最低机组人员数量的问题。

Answer 1

此问题与拓扑排序有关。

把每个作业都看作是一个图的节点。该方法的其余部分与顶级排序相同

解决问题的程序：

1. 最初，每个节点的阶数为0。

2. 现在，根据给定的作业关系更改所有节点的入级。

3. 现在，从度数为0的节点运行DFS或BFS。其余过程与拓扑排序相同。

让我们考虑一下您给定的输入。

1 -> 2

1 -> 5

2 -> 3

4 -> 2

4 -> 5

5 -> 6

inDegree[1]=0

inDegree[2]=2(1->2, 4->2)

inDegree[3]=1(2->3)

inDegree[4]=0

inDegree[5]=2(1->2, 4->5)

inDegree[6]=1(5->6)

如果我们首先从节点1运行DFS，则将其相应的节点标记为已完成则对1, 2, 3节点进行处理。作为这些之间的关系节点(1->2->3)。

注意：这里它处理的节点可以是基于关系1->5->6的1, 5, 6。它也会给出正确的答案。将首先处理哪些节点，这取决于制作邻接列表的方式。

则4将保留为未处理的节点，其入度为0。所以如果我们从4运行DFS，那么将处理4, 5, 6。As关系在这些节点之间(4->5->6)。

所以你有了答案，那就是2。

注意：处理完路径后，可以找到未处理的新节点，其阶数为0。例如，考虑关系式1->2, 2->3、2->4。

如果您首先处理路径1->2->3，则4将保持未处理状态。

如果您首先处理路径1->2->4，则3将保持未处理状态。

只需遵循基本的拓扑排序程序就会给出答案。您必须计算运行DFS的次数为0的未处理节点的数量。

学习拓扑排序的有用资源：

• 拓扑排序CP算法

• 拓扑排序GFG

• 拓扑排序教程&注释|HackerArth