設置覆蓋問題的變化（也許是活動選擇問題）

Question

每天早上9點到下午5點，我應該在工廠至少有一個人監督工人，並確保沒有任何問題。

目前ň申請人的工作，他們每個人都可以從時間工作SI時間CI，我 = 1,2，...，ñ。

我的目標是儘量減少兩個以上的人同時關注工人的時間。

（申請者提供的工作時間能夠覆蓋從上午9點到下午5點的時間段。）

我已經證明，最多兩個人都需要的任何時刻，以滿足我的需求，但如何我應該從這裏到達最終解決方案嗎？

找到只有一個人可以工作並保持工作的時間段是我的第一步，但找到下一個步驟會給我帶來麻煩......。

算法必須在多項式時間運行。

任何提示（某種類型的數據結構可能？）或引用是受歡迎的。非常感謝。

Answer 1

我想你可以通過求解子問題動態規劃做到這一點：

什麼是考慮到申請人的最小重疊時間我是最後一名工人，我們已經把所有時間從一天的開始直至ci？

調用此最小重疊時間成本值（i）。

可以通過考慮情況下計算成本（i）的值：

1. 如果SI是等於一天，然後成本（I）= 0（不需要重疊）
2. 的開始否則，請考慮所有以前的申請人j。將成本（i）設置爲成本（j）的最小值+ i和j之間的重疊。還將prev（i）設置爲達到最小值的j的值。

然後，對於您的問題的答案是由k的所有值的最小代價（k）給出，其中ck等於一天結束。您可以使用prev的值通過回溯來計算出正確的人選。

這給出了O（n^2）算法。