python - 检查时间跨度之间的重叠

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