如何證明沒有間隔重疊？

的Intervalls看起來像：

0-100 
100-200 
200-500 
500-1000 
1000-2000 ect....

眼下intervalls被單獨存儲在與分（0100200500 ...）和最大一個ArrayList（100200500 ...）

如果我添加一個新的Intervall我必須檢查是否沒有重疊現有的intervalls。例：

250-280是確定 300-600也不行

但是，我不知道該怎麼做？

來源

2012-11-10 maximus

爲什麼250-280沒問題，它與200-500重疊。 –

你如何定義重疊？ –

我會使用提供的apache IntRange解決方案[這裏]（http://stackoverflow.com/questions/8368682/how-can-i-represent-integer-intervals-in-java） – PbxMan

對於此任務，您可以使用interval tree data structure，並且僅在間隔中沒有碰撞/交點時才添加元素。

來源

2012-11-10 15:54:42 amit

使用適合查詢的數據結構幾乎總是正確的解決方案。 – eh9

您可能確實創建了一個包含開始和結束的Interval對象，該對象包含在ArrayList中。

您可以輕鬆地實現這個類的方法，可以檢測到衝突：插入你遍歷你採集和調用hasCollision（）方法之前

public boolean hasCollision(Interval inter){....}

現在... 我要優化結果，還可以使Interval對象實現Comparable並使用Sorted集合。

來源

2012-11-10 15:50:40 Frank

對於區間（A，B）

1循環列表

2如果a瀑布內部的區間中的一個，間隔重疊。

3找到它們之間兩個間隔a應該GE

4重複與b。同樣，如果b在任何時間間隔內都重疊。

5如果a和b位於它們不重疊的兩個相同間隔之間。否則它們重疊。

而且，當然，在開始算法之前，Yob建議將間隔管理爲對象的單個陣列列表使用是一個好主意。

來源

2012-11-10 15:51:57 SJuan76

眼下intervalls被單獨存儲在一個ArrayList與分鐘（0100200500 ...）和max（100200500 ...）

所以......

bool isCollided = false; 
Integer min = 250; 
Integer max = 280; 
for(Integer intOne: firstList){ 
    Integer intTwo = secondList.get(firstList.indexOf()) 
    if((min >= intOne && <= intTwo) || (max >= intOne && <= intTwo){ 
    isCollided = true; 
    break; 
    } 
}

但我可能會像其他人一樣建立自己的班級。

來源

2012-11-10 15:58:30 NimChimpsky

不要給代碼，讓新手找到他們的方式。 – SJuan76

@ SJuan76有點把這個站點的全部點都拿走 – NimChimpsky

給代碼在「我已經完成了這個程序並且我得到了這個意外的錯誤」中有意義，但是在「我不用哪個算法的時候」。 – SJuan76

由於區間不重疊，因此可以通過下限等方式對它們進行排序。要查找給定的時間間隔是否與現有時間重疊，可以使用二進制搜索，這樣搜索時間就是log（N）。

我建議創建class Interval implements Comparable<Interval>，並使用java.util.TreeMap<Integer, Interval>。關鍵是下限和上限的總和。當插入新的Interval i時，檢查重疊只有兩個條目：map.floorEntry(i.key())和map.lowerEntry(i.key())。

來源

2012-11-10 16:37:19

您可以按起始點排序。在NavigableMap。

NavigableMap<Integer, Integer> map = 
map.put(100, 200); 
map.put(300, 500); 

// to test for a range. 
int start = 300, end = 400; 
if (map.floorEntry(start).getValue() >= start && map.ceilingKey(start) <= end) 
    // out of existing ranges.

此操作爲O（LN N）

來源

2012-11-10 20:21:36

有一個簡單的方法作爲實用方法

公共靜態布爾isOverlapping（日期啓動1，日期END1，日期START2，日期END2）{ return start1.before（end2）& & start2.before（end1）; }

來源

2014-01-16 22:04:35

如何證明沒有間隔重疊？

回答

相關問題