algorithm - 非重叠区间的所有最大子集的输出敏感快速枚举

Question

因此，给定一组区间，在按区间的右端点对区间进行排序后，可以在线性时间内找到具有最大区间数的非重叠区间子集。但是，如果我们想输出具有最大数量的非重叠区间的所有解子集怎么办？运行时间应该对输出敏感，因为对于 n 个间隔，最佳解决方案的数量可能是指数级的，例如高达 O(sqrt(n)^sqrt(n))。那么，如果有 S 个最优解，它们能否在时间上与 S 的大小成线性比例地被枚举出来(也许多项式依赖于 n)？

Answer 1

为区间图中的最大独立集运行标准动态规划算法。这告诉你最大数量是多少。修改此算法以跟踪获得所述最大数的方法数很简单。

对于每个区间 I，编译所有不重叠 I 的后面区间的列表，您可以从中形成一个独立的最大大小集。

现在使用上一段中编译的信息对所有独立集运行一个简单的递归枚举。

如果最大独立集的大小是h，这将花费O(hS + n^2)时间； n^2 用于 DP，hS 用于递归和输出。