驗證數量範圍數組的最有效方法是什麼？

Question

比方說，我已經量的數組範圍：

[{min=1, max=500}, {min=2, max=1000}, ...] 

什麼是驗證該範圍不重疊（上面會驗證失敗）的最有效方法是什麼？

Answer 1

一個明顯的方法是使用區間樹並逐個插入項目。那麼檢查將是微不足道的。

另一種方法會更直接。您可以按照字典順序排列數組，並保持最左邊的可用起點。當一個新的時間間隔到來時，它必須在這一點之後開始（我們不介意這些間隙，因爲數組已經排序，並且間隙永遠不會再被訪問）。

def validate(listoftuples): 
    rightedge = -10000000000000000 # some kind of minus infinity 
    listoftuples.sort() 
    valid = True 
    for l, r in listoftuples: 
     if l >= rightedge: 
      rightedge = r 
     else: 
      valid=False 
      break 
    return valid 

validate([(1, 500), (2, 1000)] 
>>> False 
validate([(1, 2), (2, 1000)]) 
>>> True 

這兩個都在O(N log N)時間運行。我不確定是否可以做得更好。