覆蓋所有子陣列的最小集合

Question

我用很少的修改來解釋這個問題，這樣它就變得很容易解釋。

有ñ僱員，我需要安排他們在這樣的一個月的所有（或最多）員工可用於出遊的一天郊遊。

要求每位員工填寫在線調查，說明他的可用性，例如， 1-31或15-17等等。甚至有一天也可能無法使用。 我不得不爲整個員工安排的行程數量沒有限制（不考慮整個月沒有人可用），但我想找出最少的一組日期以涵蓋所有員工。所以在最壞的情況下，我將不得不安排旅行31次。

問題：什麼是我可以用來在這個數據結構上運行最佳擬合算法的最佳數據結構？解決這個問題最好的辦法是什麼？

通過最好的，當然我的意思是時間和空間有效的方式，但我也在尋找其他的選擇來解決這個問題。

我的思維方式是維持一個數組31個整數並初始化爲在每個員工的0.1運行，並根據他們的可用日期遞增數組索引。最後，對31的數組進行排序。最大值代表最大員工可用的日期。對左派員工應用相同的邏輯。但問題是要排除被遺漏的員工。爲此，我將不得不遍歷整個員工名單，以瞭解哪些員工可以被刪除，並形成一個新的員工名單，我可以應用先前的邏輯。根據我的說法，這樣兩次在列表中移除這些員工並不是最好的選擇。有任何想法嗎？

Answer 1

作爲第一步，您應該排除沒有可用日期的員工。

然後你問題就變得Set Cover Problem的變體。

你的宇宙U全體員工，以及套S藏品天。對於每天i，如果該員工在第i日可用，則您有員工j處於集合S[i]中。

這個問題是NP難的。所以，除非你想要一個近似的解決方案，你必須檢查每個31^2天的組合，可能有一些修剪。

Answer 2

選擇從1到31的陣列（每個索引代表一個月份的日期）。對於你必須創建一個鏈表（雙）每一日期，包含誰可在該天中的emp_id（你可以同時創建此列表將根據emp_id進行排序，並且您可以保留關於列表大小以及最大員工數組索引的信息）。 最大的列表必須在解決方案中（以第一個日期爲準​​）。 現在將每個列表與最大列表進行比較，並從列表中刪除那些已經存在於所選最大列表中的員工。 現在執行相同的程序，找到第二個日期等等...... 這整個程序將在O（n^2）中運行（因爲31是一個常數值）。 和空格將是O（n）。