迷惑分區域列表中的覆蓋區域

Question

我有一個很長的值列表x和y，按x值排序。我想輸出x和y值最長連續跨度的列表。這是有點難以付諸話但將有希望成爲用下面的例子清楚：作爲5768和6000之間的區域沒有被任何條目的覆蓋，上述應

0, 148 
0, 145 
0, 186 
0, 5768 
600, 2374 
2376, 2415 
3000, 4315 
6000, 6616 
6000, 6799 
6000, 7262 

輸出：

0, 5768 
6000, 7262 

在我看來，這應該是一個簡單的問題，但我一直沒有解決方案的工作一段時間。我已經在下面發佈了我的代碼。 我目前的努力存在的問題是，雖然對x值進行排序，但可能是第k行的x值超過第k-1行的y值，但不標記新連續字符串的開始。

lines = [line.strip('\n') for line in open('test')] 
myarray=[] 
for line in lines: 
    myarray.append(line.split(', ')) 

def findCoveredRegions(regionArray): 
    resultsContigs = [] 
    j = regionArray[0][1] 
    i = regionArray[0][0] 
    for line in regionArray: 
     last_i = i 
     i = line[0] 
     if i <= j: 
      if line[1] > j: 
       j = line[1] 
     else: 
      resultsContigs.append([last_i,j]) 
    resultsContigs.append([i,regionArray[len(regionArray)-1][1]]) 

    return resultsContigs 

print findCoveredRegions(myarray) 

Answer 1

這裏是一個numpy的解決方案

myarray = np.asanyarray(myarray) 
order = np.argsort(myarray.ravel()) 
coverage = np.add.accumulate(1 - 2*(order%2)) 
gaps = np.where(coverage==0)[0] 
left = order[np.r_[0, gaps[:-1] + 1]] 
right = order[gaps] 
result = myarray.ravel()[np.c_[left, right]] 

它池和排序的所有邊界。然後從左到右計算它遇到的左（+1）和右（-1）邊界的數量。這個數字永遠不會是負數，只有在存在差距時纔會降到零。從間隙位置重建覆蓋間隔。

Answer 2

這不會特別快，但我認爲這是相當Pythonic和可讀性。它不需要或使用排序的間隔列表。

intervals = [(0, 148), 
(0, 145), 
(0, 186), 
(0, 5768), 
(600, 2374), 
(2376, 2415), 
(3000, 4315), 
(6000, 6616), 
(6000, 6799), 
(6000, 7262)] 


def intersect(interval_a, interval_b): 
    """Return whether two intervals intersect""" 
    (a_bottom, a_top), (b_bottom, b_top) = interval_a, interval_b 
    return a_bottom <= b_top and b_bottom <= a_top 


def union_one_one(interval_a, interval_b): 
    """Return the union of two intervals""" 
    (a_bottom, a_top), (b_bottom, b_top) = interval_a, interval_b 
    return min(a_bottom, b_bottom), max(a_top, b_top) 


def union_many_one(old_intervals, new_interval): 
    """Return the union of a new interval with several old intervals.""" 
    result = [] 
    for old_interval in old_intervals: 
     # If an old interval intersects with the new interval, merge the old interval into the new one. 
     if intersect(old_interval, new_interval): 
      new_interval = union_one_one(old_interval, new_interval)  
     # Otherwise, leave the old interval alone. 
     else: 
      result.append(old_interval) 
    result.append(new_interval) 
    return result 


def union_all(intervals): 
    """Return the union of a collection of intervals""" 
    result = [] 
    for interval in intervals: 
     result = union_many_one(result, interval) 
    return result    


print(union_all(intervals))