劃分一維空間的算法

我對應於相同的一維（線性）空間的兩組區間。這是一個粗略的視覺效果 - 事實上，有更多的間隔，他們更分散，但是這給出了基本的想法。劃分一維空間的算法

interval graphic

這些區間的每一箇中包含的信息，和我寫一個程序將信息存放在一個設定的時間間隔（紅色），以包含在另一組（藍色）的信息進行比較。

這是我的問題。我想將空間劃分爲n塊，以便在每個塊中進行大致相同量的比較工作（工作量取決於該空間部分中的間隔數）。此外，該分區不應該在兩個塊之間分割任何紅色或藍色間隔。

所以輸入是兩組間隔的，並且所期望的輸出是空間這樣的一個分區，它

的間隔（大致）相等地隔着分隔
沒有間隔的每個元素分佈與多個分區元素重疊

任何人都可以提出一個方法或算法來做到這一點？

來源

2011-04-01 Daniel Standage

@Daniel：爲了構建一個比較列表，在開始比較之前掃描整個空間是否昂貴？此外，你保證有相同數量的紅色和藍色間隔？是否有任何方法通過檢查來區分間隔的序列（例如，在標頭或其他內容中編碼的序列號）？ – 2011-04-01 03:19:42

可能不會有相同數量的間隔。線性空間的快速初始掃描可能需要並且不會很昂貴。如果需要，我可以在多個數據結構中存儲指向「間隔」對象（具有開始和結束座標的對象）的指針，儘管這會佔用太多內存以至於不能存儲更多內存。一個間隔樹和一個動態數組首先浮現在腦海中，但我試圖弄清楚如何使用它們...... – 2011-04-01 03:34:27

@Daniel - 我是否錯過了一些東西，或者你不能僅僅創建一個指針對列表快速掃描，然後分割該列表進行處理？ – 2011-04-01 03:44:38

將「單詞」定義爲每個點屬於紅色間隔或藍色間隔的最大間隔。沒有塊可以在一個詞的中間結束，並且每個連續詞的聯合是潛在的塊。現在將一個minimum raggedness word-wrap algorithm應用於單詞，其中單詞的長度被定義爲它包含的時間間隔數（行=大塊）。

來源

2011-04-03 20:16:29 qrqwe

使用這個的棘手部分是猜測導致需要n行的行寬。 – 2011-04-03 20:24:20

問題的其餘部分使得這聽起來像一個軟約束。更緊迫的是是否允許非連續分區的問題。 – qrqwe 2011-04-03 20:31:40

是的，次優但接近最優的解決方案是可以接受的，但是「單詞」必須按排序順序維護。 – 2011-04-04 11:12:43

劃分一維空間的算法

回答

相關問題