我已经给出了一些间隔I = {I(1), I(2), ..., I(m)}。I(i) = [a_i, b_i] (1<=a_i<=b_i<=n)您可能会认为间隔相互覆盖（对不起，我的英语很差），所以没有间隔，例如{[1,5], [3,6]}, {[2,5], [5,7]}. 并且{[1,1], [2,2], ..., [n,n]}必须包含在 I 中。
让我们假设C(i) = b_i - a_i + 1。
我想找到{I(c_1), I(c_2), ..., I(c_k)}彼此不重叠的，并且C(c_1) + C(c_2) + ... + C(c_k) = T. (1 <= T <= n).
我可以使用子集和问题找到O(n*T)DP 解决方案，我认为它是 NP，但我不确定。我可以优化更多O(n*T)吗？
这个问题可以从子集和问题（给定一组数字和一个目标数字，找出是否有一个子集与这个目标相加）通过简单的归约：
给定一个子集和的实例：S={c_1,c_2,..,c_n},T- 通过创建n非重叠区间、区间 i 和c_i点来创建这个问题的一个实例（通过升序很容易做到）。还是一样T。
现在，子集和问题的答案是正确的当且仅当存在一个总和为 的区间子集T。这基本上是同一个问题，因为根据问题的定义，所有区间都不会相互重叠。
由此我们可以得出结论-您的问题是NP-Hard。
此外，如果我们能更好地解决问题 then O(T*n)，我们可以使用相同的方法解决子集和问题，然后O(T*n)1,2。
但是，AFAIK，子集和的最佳伪多项式解决方案是O(T*n)，所以如果你有这样的解决方案 - 坚持下去。
(1) 转换问题是O(n)
(2) 这种说法仅适用于这种特定的归约，而不适用于多项式归约的一般情况。