檢查時間跨度之間的重疊

Question

我有一個開始時間和停止時間條目（HHMM格式）的列表。如果列表中存在重疊或不存在，我無法確定如何在Python中對其進行編碼。

例

 
Entry 1: 1030, 1245; 
Entry 2: 1115, 1300 
== True 

Entry 1: 0900, 1030; 
Entry 2: 1215, 1400 
== False 

Answer 1

首先我們排序的開始時間列表。

然後我們循環檢查下一個開始時間是否低於上一個結束時間。

這將檢查如果x + 1，其中x重疊（如果x + 2 X不重疊等）

intervals = [[100,200],[150,250],[300,400]] 
intervalsSorted = sorted(intervals, key=lambda x: x[0]) # sort by start time 
for x in range(1,len(intervalsSorted)): 
    if intervalsSorted[x-1][1] > intervalsSorted[x][0]: 
     print "{0} overlaps with {1}".format(intervals[x-1], intervals[x]) 

# result: [100, 200] overlaps with [150, 250] 

下應該給你整個列表中的所有的重疊。

intervals = [[100,200],[150,250],[300,400],[250,500]] 

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] ] 
for x in overlapping: 
    print '{0} overlaps with {1}'.format(x[0],x[1]) 

# results: 
# [100, 200] overlaps with [150, 250] 
# [250, 500] overlaps with [300, 400] 

請注意，這是一個O（n * n）查找。 （有人糾正我，在這裏，如果我錯了！）

這可能是比第一更慢（沒有測試它，但我相信它是），因爲這遍歷整個列表中爲每個單項指標。應該類似於arbarnert的嵌套for循環示例。但話又說回來，這也給你所有的重疊值相對於第一種方法我表明，只有檢查的旁邊（按開始時間排序）之間的重疊時間。

擴展測試得出：

intervals = [[100,200],[150,250],[300,400],[250,500],[10,900],[1000,12300],[-151,32131],["a","c"],["b","d"],["foo","kung"]] 

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] ] 
for x in overlapping: 
    print '{0} overlaps with {1}'.format(x[0],x[1]) 

# results: 
# [100, 200] overlaps with [150, 250] 
# [250, 500] overlaps with [300, 400] 
# [10, 900] overlaps with [100, 200] 
# [10, 900] overlaps with [150, 250] 
# [10, 900] overlaps with [300, 400] 
# [10, 900] overlaps with [250, 500] 
# [-151, 32131] overlaps with [100, 200] 
# [-151, 32131] overlaps with [150, 250] 
# [-151, 32131] overlaps with [300, 400] 
# [-151, 32131] overlaps with [250, 500] 
# [-151, 32131] overlaps with [10, 900] 
# [-151, 32131] overlaps with [1000, 12300] 
# ['a', 'c'] overlaps with ['b', 'd'] 

Answer 2

假設你有一個intervals_overlap(interval1, interval2)功能...

的第一個想法是在列表中的每對間隔的天真迭代：

for interval1 in intervals: 
    for interval2 in intervals: 
     if interval1 is not interval2: 
      if intervals_overlap(interval1, interval2): 
       return True 
return False 

但是你應該能夠找出更聰明的辦法來解決這個問題。

Answer 3

以供將來參考，@Roy的解決方案不適用於具有相同或年底開始時間間隔工作。以下解決方案可以：

intervals = [[100, 200], [150, 250], [300, 400], [250, 500], [100, 150], [175, 250]] 
intervals.sort() 
l = len(intervals) 
overlaps = [] 
for i in xrange(l): 
    for j in xrange(i+1, l): 
    x = intervals[i] 
    y = intervals[j] 
    if x[0] == y[0]: 
     overlaps.append([x, y]) 
    elif x[1] == y[1]: 
     overlaps.append([x, y]) 
    elif (x[1]>y[0] and x[0]<y[0]): 
     overlaps.append([x, y]) 

此外，Interval Tree可用於這些類型的問題。

Answer 4

簡單的方式來做到這一點：

我換號轉換爲字符串，因爲第3項中含有0900這是無效的。

entry01 = ('1030', '1245') 
entry02 = ('1115', '1300') 

entry03 = ('0900', '1030') 
entry04 = ('1215', '1400') 

def check(entry01, entry02): 
    import itertools 
    input_time_series = list(itertools.chain.from_iterable([entry01, entry02])) 
    if input_time_series != sorted(input_time_series): 
     return False 
    return True 

>>> check(entry01, entry02) 
False 
>>> check(entry03, entry04) 
True 

Answer 5

爲了擴大對@羅伊的答案，包括其中一些具有相同的時隙的情況下，你需要區分：

intervals = [[100,200, "math"],[100,200, "calc"], [150,250, "eng"],[300,400, "design"],[250,500, "lit"],[10,900, "english"],[1000,12300, "prog"],[-151,32131, "hist"]] 

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] or x[0]==y[0] and x[1]==y[1] and x is not y] 
for x in overlapping: 
    print '{0} overlaps with {1}'.format(x[0],x[1]) 


# Prints 
#[100, 200, 'math'] overlaps with [100, 200, 'calc'] 
#[100, 200, 'math'] overlaps with [150, 250, 'eng'] 
#[100, 200, 'calc'] overlaps with [100, 200, 'math'] 
#[100, 200, 'calc'] overlaps with [150, 250, 'eng'] 
#[250, 500, 'lit'] overlaps with [300, 400, 'design'] 
#[10, 900, 'english'] overlaps with [100, 200, 'math'] 
#[10, 900, 'english'] overlaps with [100, 200, 'calc'] 
#[10, 900, 'english'] overlaps with [150, 250, 'eng'] 
#[10, 900, 'english'] overlaps with [300, 400, 'design'] 
#[10, 900, 'english'] overlaps with [250, 500, 'lit'] 
#[-151, 32131, 'hist'] overlaps with [100, 200, 'math'] 
#[-151, 32131, 'hist'] overlaps with [100, 200, 'calc'] 
#[-151, 32131, 'hist'] overlaps with [150, 250, 'eng'] 
#[-151, 32131, 'hist'] overlaps with [300, 400, 'design'] 
#[-151, 32131, 'hist'] overlaps with [250, 500, 'lit'] 
#[-151, 32131, 'hist'] overlaps with [10, 900, 'english'] 
#[-151, 32131, 'hist'] overlaps with [1000, 12300, 'prog']