我給了I(i) = [a_i, b_i] (1<=a_i<=b_i<=n)的一些間隔I = {I(1), I(2), ..., I(m)}。你可能認爲這些間隔覆蓋對方（對不起，我英文很差），所以沒有間隔，如{[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)嗎？
的問題是reduceable從Subset Sum problem（給定一組數字和一個目標數字，找出是否有是總計爲這一目標的一個子集），用一個簡單的reduction：
鑑於subset-的實例總和：S={c_1,c_2,..,c_n},T - 通過創建n非重疊區間，間隔i，用c_i點（易於按升序執行）創建此問題的實例。保留相同的T。
現在，當且僅當存在總和爲T的區間的子集時，子集和問題的答案纔是真的。這基本上是同樣的問題，因爲根據問題的定義，所有間隔都不會相互重疊。
由此我們可以得出結論 - 您的問題是NP-Hard。此外，如果我們可以更好地解決問題然後O(T*n)，我們可以使用相同的方法來更好地解決子集總和問題，然後O(T*n)1,2。
但是，AFAIK，子集總和的最佳僞多項式解決方案是O(T*n)，所以如果你有這樣的解決方案 - 堅持下去。
（1）轉換問題是O(n)
（2）本權利要求是真正的用於該特定單獨減少，而不能用於多項式削減的一般情況。
我添加了一些術語，你能檢查它也是NP嗎？我不確定。 –
@LovePaper：你的意思是NP-Hard？還是NP？ （可以在非確定性圖靈機中多項式求解）？我已經表明它是NP-Hard，如果它在NP中，我需要考慮一下，但是我的直覺是這麼說的。 – amit
歡迎來到堆棧溢出。你能告訴我們你到目前爲止做了什麼嗎？ – Luca
查找是否存在一個間隔的子集，使得「C（d_1）+ C（d_2）+ ... + C（d_k）」僅是NP-Hard（子集和問題），並且解決它的一般方法是使用'O（mT）'DP解決方案，一個指數蠻力 – amit