我有一个时间条目列表（HHMM格式），其中包含开始时间和停止时间。我很难弄清楚如何用Python对它进行编码，如果列表中有重叠或没有重叠，它就会返回。
示例
条目1:10301245；条目2:11151300==正确条目1:09001030；条目2:1215400==错误
首先，我们根据开始时间对列表进行排序。
然后我们循环检查下一个开始时间是否低于上一个结束时间。
这将检查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']
为了将来参考，@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])
此外，区间树也可以用于这类问题。
要扩展@Roy的答案，包括某些东西具有相同时隙并且需要区分的情况：
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']
假设您有一个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
但你应该能够想出更聪明的方法来解决这个问题。
简单的方法：
我将数字更改为字符串，因为条目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