检查时间跨度之间的重叠

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']