我已重疊的間隔的排序列表，間隔從不包含在彼此，例如，算法移位重疊的間隔，直到沒有重疊左
[(7, 11), (9, 14), (12, 17)]
用於輸出該約束到每個元素保持作爲儘可能靠近其原點（間隔的中間） ，保留輸入的順序，並刪除所有重疊。只需要一個 近似解決方案。對於例如輸入預期的結果將是：
[(5,9), (9, 14), (14, 19)]
我只知道去這在一些模擬 風格的解決方案：在無方向的每個元素通過一定的價值轉移和 迭代，直到所有重疊已被刪除。
有沒有現有的算法來解決這個問題？
找到整體平均：
(7 + 11 + 9 + 14 + 12 + 17)/6 = 11.667
找到的總長度：
在我們的例子中(11-7) + (14-9) + (17-12) = 4 + 5 + 5 = 14;
發現新的最小值/最大值;
14/2 = 7
11.667 - 7 = 4.667
11.667 + 7 = 18.667
可以圓「時間
4.667 ~ 5
18.667 ~ 19
開始從分鐘，由間隔創建部分
(5, (11-7)+5) = (5,9)
(9, (14-9)+9) = (9,14)
(14, (17-12)+14) = (14,19)
注：
這種方法不會保留元素儘可能與原件平等，但會盡可能地使它們儘可能地接近原件繼承人相對值（維護中心）
編輯：如果你想保持儘可能接近原來的所有間隔的平均值
，可以實現數學的解決方案。
我們的問題的輸入是：
一個 =（一個 1,1，一個 1,2-），...，一個Ñ =（一個 N，1，一個 N，2-）
我們將定義：
人工智能 =一個 1,2- -a 1,1 //定義間隔
b =（d，d + ai ）
b Ñ =（d +總和（AI ..ai N-1），d +總和（AI ..ai Ñ））
雙向 = b 1,2- -b 1,1- //定義的間隔
我們需要找到一個 'd'，如：
S =總和（ABS（（一個 1,1 +一個 1,2-）/ 2 - （B 1,1 + b 1,2-）/ 2））
分鐘（S）是我們想
在我們的例子：
一個 =（7,11），噯 = 4，A AVG1 = 9
一個 =（9,14），噯 = 5，A AVG2 = 11.5
一個 =（12,7），噯 = 5，A avg3 = 14.5
b =（d，d + 4）乙 AVG1 = d + 2
b =（d + 4，d + 9）乙 AVG2 = d + 6.5
b =（d + 9，d + 14）乙 avg3 = d + 11.5
S = ABS（9-（d + 2））+ ABS（11.5-（d + 6.5 ））+ abs（14.5-（d + 11。5））= ABS（7-d）+ ABS（5-d）+ ABS（3-d）
現在calculcate衍生物找到最小/最大OR迭代過d得到的結果。在我們的例子中，你需要重複3至7
應該做的伎倆
鑑於該解決方案必須保留順序，我們可以提出這個問題作爲一個線性規劃。讓[i i，b i]成爲第i個間隔。令變量x i是第i個區間的左移，y i是第i個區間的右移。
最小化總和我（X 我 + Y 我）
受
（*）所有的i：乙我 - X 我 + Y 我≤一個 i + 1的 - X i + 1的 + Y i + 1的
對於所有的i：X 我，y i≥0
通過引入變量z來重寫約束（*）i。
對於所有的i：X 我 - ý我 - X i + 1的 + Y i + 1的 - z 我 = 0
對於所有的i位：Z 我≥b 我 - 一個 i + 1的
現在問題減小到計算minimum-cost circulation，可以在聚時間來完成。不過，我有一種感覺，這個問題有更直接的解決方法。
圖表看起來像
(*)
---- | ----
/ z| \
/ i| \
/ xi | xi+1 \
|/ <---- v <---- \|
... (*) ...
----> ---->
yi yi+1
平均數是你想要的，我的意思是，如果你想讓它儘可能接近原來的 – galchen
是每一個新的區間應該等於相應中點中點舊的？ –
一個間隔可以包含在另一個內嗎？是否有必要保留列表中的間隔順序？ – Per