區間調度的不同版本

-2

給定n個區間和一個數k，給出一個算法來找出區間的最大子集，使得其中不超過k個點中包含點。我們知道當k = 1時，這個問題可以通過貪婪算法來解決。所以我一直在試圖爲上述問題開發一個貪婪算法。區間調度的不同版本

2016-09-26 Eric mingjie

我會這樣做的方法是首先獲取所有間隔的所有邊界的集合，然後對該集合進行排序。這可能是至多n * 2點x_i的集合。然後考慮集合S_i = [x_i，x_ {i + 1}]。每個起始間隔包含S_i或不相交。因此，對於每個S_i，我們可以構建包含該集合的所有區間索引的列表T_i。所以它間隔1,2,5與集合S_1相交比T_1 = {1,3,5}。

我們現在有一組集合T_i，問題簡化爲找到最小集合M，使得T_i並集M對每個T_i至多有k個元素。我們可以通過扔掉T_i來簡化問題，T_i以少於k個項目開始。

遞歸算法應該能夠通過可能的套做一個貪婪搜索M.

來源

2016-09-26 15:51:34

感謝很多的answer.That是一個絕妙的主意！但是最後我還是要檢查所有可能的套M，這需要很多時間。 –

區間調度的不同版本

回答

相關問題