找到所需人數的最佳方式

我有一些每日數據，包括行動的開始時間和結束時間。每個行動都需要一個人。我想知道我需要多少人。找到所需人數的最佳方式

下面是數據的一個例子（我使用python）：

[str(d.start) + " || " + str(d.end) for d in dailyJobs] 

>> ['2013-08-09 07:30:00 || 2013-08-09 11:45:00', 
    '2013-08-09 07:25:00 || 2013-08-09 10:45:00', 
    '2013-08-09 07:35:00 || 2013-08-09 10:35:00', 
    '2013-08-09 09:35:00 || 2013-08-09 12:05:00', 
    '2013-08-09 10:15:00 || 2013-08-09 13:20:00', 
    '2013-08-09 09:15:00 || 2013-08-09 12:55:00', 
    '2013-08-09 12:35:00 || 2013-08-09 15:35:00', 
    '2013-08-09 13:05:00 || 2013-08-09 15:25:00', 
    '2013-08-09 17:10:00 || 2013-08-09 18:32:44']

這是問題的甘特圖： Gantt-chart

我們可以看到，6個行動將完成在同一時間。所以我們需要6人。

我的解決方案

我可以遍歷每分鐘檢查時間段我在數量，最大將是需要人的最低數量。

我正在尋找更好的算法來實現這一點。

來源

2014-04-22 Paul Fournel

請說清楚你的問題 –

我會做一個甘特圖，它會幫我解釋一下。 –

你看過那個嗎？ http://stackoverflow.com/questions/18365107/maximum-no-of-overlaps-of-all-time-intervals – user189

讓我說明我的想法，看看是否適合。設L是非重疊時間範圍的有序列表和計數。最初L是空的。

L: [ c ][  c ][ c ][  c  ] 
d:   [     ]

結果：：

對於dailyJobs每個時間範圍d，d可以在L.

例如與一些時間範圍重疊

L: [ c ][c ][c+1 ][c+1][c+1 ][ c  ]

即合併L和d st L仍然是非重疊時間範圍的有序列表。在迭代dailyJob中的所有d之後，遍歷L中的條目以獲取最大值。計數。

當然，你也可以保留一個maxCount變量s.t.在L和d的每次合併中，您都將此變量保留爲最大計數s.t.您可以避免最後的O（n）掃描。

來源

2014-04-22 09:24:59

找到所需人數的最佳方式

回答

相關問題