解決重疊的項目

的堆疊順序我有Foo具有這些特性的列表：解決重疊的項目

class Foo 
(
    Date From 
    Date To 
    int Importance 
)

這些項目的From和To日期可以重疊。在兩個foos重疊的情況下，具有最高Importance的foo優先於其他項目。

是否有一個優雅的算法來獲取Foo列表並通過使用上述規則解決任何重疊（通過確定哪個Foo具有最高的因子）？我迄今爲止的嘗試都很難看。最終，他們會針對每個可能的重疊衝突進行一系列檢查，例如較低優先級的foo之前的較高優先級，出現在較低優先級foo的範圍中間的較高優先級foo等等。這樣的策略看起來難以維持，並且尋求一種我尚未發現的更優雅的方法。

最大的問題在這裏是一個更高的優先級Foo可以細分低優先級的一個，所以我們不能簡單地調整相沖突Foos的From和To點。

來源

2011-07-20 duck9

請指定解決重疊的含義。 –

我已經編輯過。對於'Foo'序列，在給定的時間只能應用一個'Foo'。通過「解決」重疊，我的意思是確定哪個「Foo」在每個衝突中具有最高的「重要性」因子並忽略其他的「Foo」。 – duck9

謝謝 - 你提到調整'From'和'To'，所以看起來好像還有一些重新安排。 –

您可以使用優先級隊列。

生成所有三元組（日期，BOOL，INT），其中第一個參數是一個或從FOOS之一，布爾的屬性表明它是否是一個爲（true）還是從（假）和INT一個是優先事項。
按日期排序這些對的列表
創建由重要性排序的三元組的空優先級隊列。
遍歷排序列表和每個三元組（迄今爲止，這一領域的空白，重要性）做：

一個。如果它是From（isTo = false），則添加到隊列

b。如果它是一個爲（ISTO =真），然後從隊列

隨時移除隊列中的最大元素（你可以在O查找（1））包含一個誰該時間獲勝。

（如果您需要實際的Foo對象，只需將三元組引用到Foo即可）。

來源

2011-07-20 06:54:37

我也會使用Priority Queue，就像Petar一樣，但我會將所有Foo元素存儲在其中。該隊列中的優先級爲：第一個 - 起始日期，第二個到日期，第三個「優先級」（我的意思是首先根據from字段「排序」所有元素，然後根據字段根據優先次序持續到領域）。在完成優先級隊列之後，您可以簡單地遍歷它，檢查每對元素之間的「距離」是否相同（距離是（（To1-To2）+（From1-From2））。找到這樣的一對留下第一個項目並刪除第二個項目，實際上你可以在創建隊列或插入新項目時做到這一點，如果我是正確的，整個算法就是O（nlogn）。

@編輯：哦，對不起，我是在我的早晨咖啡之前，我以爲你的意思是2 Foos有相同的To和From，我現在明白你也想刪除以下情況下的項目：
Foo1從5到10優先級1
Foo2從1到11優先級2
什麼是「封閉」Foo（即1-11）具有較低的優先級？

@編輯2：好吧還好我的算法稍作調整應該工作。而不是t1-t2 + f1-f2就像我上面提到的那樣對它們進行排序，並檢查每一對F2（來自foo2）是否在T1和F1之間。如果是，則刪除Foo2。

實施例：
Foo1：3至4個優先級1
foo2的：從5到6優先級2
Foo3：從1到7優先級3

優先之後將是：
Foo3 - > Foo1 - > Foo2
首先你檢查Foor3和Foo1，From of Foo1在Foo3的From和To之間，因此你刪除了Foo1，因爲它具有較低的優先級（可以說在這種情況下越好越好）。然後你檢查Foo3和Foo2（你會檢查Foo1和Foo2是否被刪除）。再次檢查From of Foo2是否在From和From Foo3之間，因爲它是刪除Foo2。
整個算法仍然是O（nlogn）。如果我沒有看到一些會失敗的情況，請給我留言。

來源

2011-07-20 07:26:46

使用優先級隊列。按importance排序，然後按from，然後按to排序。現在，您提取的每個foo都將清除（不衝突）或與相同或更高優先級foo相交。按順序解決衝突，完成！

來源

2011-07-20 22:07:40 MSN

解決重疊的項目

回答

相關問題