任务序列排序问题：如何判定无中断任务序列的可排序性？

问题定义 #

给定一组包含整数值（每个整数对应一个任务）的集合序列S，需对S中的集合重排，满足无中断任务约束：对于任意任务x，所有包含x的集合在重排后的序列中必须形成连续块（即含x的集合不能被不含x的集合隔开）。

示例说明 #

• 示例1
  原始集合：S = {S₁={1,5}, S₂={1,3,4}, S₃={5}}
  • 不合法排序：S₁→S₂→S₃（任务5的集合S₁和S₃被S₂隔开）
  • 合法排序：S₃→S₁→S₂
• 示例2
  原始集合：S = {S₁={1,2,3}, S₂={2,4}, S₃={4,5}}
  • 已为合法排序（任务2的集合S₁、S₂连续；任务4的集合S₂、S₃连续；其余任务仅出现在单个集合中）
• 示例3
  原始集合：S = {S₁={1,2}, S₂={2,3}, S₃={1,3}}
  • 不存在合法排序（无论如何排列，总有某个任务的集合被隔开）
• 示例4
  原始集合：S = {S₁={1,2,3}, S₂={5,6,7}, S₃={3,6}}
  • 合法排序：S₁→S₃→S₂（任务3的集合S₁、S₃连续；任务6的集合S₃、S₂连续）

问题建模 #

该问题可直接转化为二分矩阵的连续1问题：

1. 构建矩阵M：
   • 行：对应每个任务（整数）
   • 列：对应每个集合S_i
   • 元素M[x][S_i] = 1当且仅当任务x属于集合S_i，否则为0
2. 原问题的合法排序等价于：能否对矩阵的列（集合）重排，使得每一行（任务）中的所有1都连续排列。

可判定性算法（无需执行排序） #

针对连续1问题，已有成熟的线性时间判定方法：

1. PQ树约束验证 #

PQ树是一种维护元素连续约束的数据结构，验证步骤如下：

• 初始化PQ树，将所有集合作为叶子节点
• 对每个任务x对应的行，向PQ树施加约束：所有含x的集合必须连续
• 若所有约束都能被PQ树接受（树未被标记为无效），则存在合法排序；否则不存在。

2. 禁止子矩阵检测 #

连续1问题的充要条件是：矩阵中不存在交替子矩阵——即不存在四个列a,b,c,d和两个行x,y，满足：

• M[x][a] = M[x][d] = 1，M[x][b] = M[x][c] = 0
• M[y][b] = M[y][c] = 1，M[y][a] = M[y][d] = 0
  若检测到此类子矩阵，则无合法排序；反之则存在。

多元素集合的扩展思路 #

当每个集合仅含两个元素时，矩阵每行最多两个1，可简化为检查对应图是否为区间图；但扩展到三个及以上元素时，必须使用通用的连续1问题判定算法（如PQ树），因为此时任务对应的行可能有多个1，需保证这些1在列排列中连续。

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