分配问题：求最小作业序列数，最大基数匹配能否得到最优解？

结论先行 #

你描述的问题属于有向无环图(DAG)的最小不相交路径覆盖问题，通过最大基数匹配得到的结果完全可以对应最小的作业序列数，二者有严格的数学对应关系：

最小作业序列数 M = 作业总数量N - 对应二分图的最大基数匹配数

原理说明 #

最小不相交路径覆盖的定义是：用最少的互不相交的路径覆盖DAG的所有顶点，每条路径上的顶点顺序符合边的指向，对应你场景里的作业先后顺序。

注：如果作业先后规则存在循环依赖（比如A可接B、B可接A），需要先对强连通分量做缩点处理，将原图转换为DAG后再继续后续流程。

该问题转换为二分图最大匹配的逻辑如下：

• 把每个作业拆为二分图的左、右部两个独立节点
• 若原规则中作业A后续可接作业B，就在二分图中添加左部A到右部B的边
• 求解该二分图的最大基数匹配：每匹配成功一条边，就代表两个作业可以拼接在同一条序列里，总序列数就减少1
• 最终最小序列数就是总作业数减去最大匹配数

示例验证 #

你给出的N=6的案例中，二分图的最大匹配数为4（匹配对为1→2、2→3、4→5、5→6），代入公式得M=6-4=2，和你给出的最优结果完全一致。

可用算法 #

• 小规模场景直接使用匈牙利算法求解二分图最大匹配即可，实现简单
• 作业数量超过1000的大规模场景，推荐使用Hopcroft-Karp算法，时间复杂度更低

内容的提问来源于stack exchange，提问作者anh123minh