查找一系列間隔的最有效分組

Question

我有一個應用程序，其中有一系列不重疊的固定寬度間隔，每個間隔都有一個給定的鍵。每個區間具有相同的寬度，並且可能有連續的區間。本質上，我想以這樣一種方式將區間和鍵組合在一起，以使單獨區間的數量最小化。這可以通過將相同的間隔合併到相同的密鑰或尋找匹配的間隔並將它們組合成具有多個密鑰的單個間隔來完成。我目前的算法嘗試了上述兩種方法，並且看到哪些結果的間隔數最少，但是我覺得必須有一種更明智的方法來解決問題。任何意見將不勝感激！

例如：

| ----- | | ----- |間隔帶鍵k1（連續）

| ----- |間隔帶密鑰k2

| ----- |間隔與密鑰k3

在這個問題中，密鑰k1的間隔可以合併爲一個連續的間隔，導致3而不是四個總間隔。或者每個關鍵字k1，k2和k3的第一個間隔可以與關鍵字k1，k2和k3組合成一個間隔，從而產生一個間隔加上k1中的第二個剩餘間隔。

最糟糕的情況會是70,000間隔。

Answer 1

一個好的近似解決方案的想法。由於固定寬度輸入數據的間隔可以用一個（X）軸上的間隔和其他（Y）軸上的間隔表示爲位掩碼。對於你的數據，如：

k3 1 0 
k2 1 0 
k1 1 1 
    i1 i2 

問題是類似的，用於分隔rectilinear polygon問題。有一個非常好的答案，涵蓋了topic。

這是不準確的問題，因爲在按鍵的這種情況下，順序並不重要，有什麼可以例子看出：

k3 1 1 
k2 1 0 
k1 1 1 
    i1 i2 

分區會產生可以使用3個矩形結果，而解決方案應該是2

簡單的解決方案（近似）是使輸出後處理和連接矩形在相同的間隔。這將有助於對鍵進行重新排序的預處理，以便具有類似「覆蓋」的鍵更近或鄰居。

更復雜的解決方案是（我不是100％它的工作原理）是使用算法分割直線多邊形的想法。想法是：

• 採取的所有可能分割（簾線），
• 創建具有簾線作爲頂點和邊，其中簾線相交曲線圖，
• 找到最大（線）independent set。

在原始情況下，每個內部（270度）拐角在兩個方向上產生兩根簾線。由於鍵排序並不重要，因此我認爲Z鍵應該貫穿整個「幾何形狀」。這意味着簾線是：

• 一個鍵繼續間隔（X方向）
• 間隔的端部（Z軸方向，通過整體的幾何構圖）。