检查时间跨度之间的重叠

问题描述

我有一个带有开始时间和停止时间的时间条目列表(HHMM 格式).我无法弄清楚如何在 Python 中对其进行编码，如果列表中存在重叠或不存在，则返回.

示例

条目 1:1030、1245；条目 2:1115、1300== 真条目 1:0900、1030；条目 2:1215、1400== 错误

解决方案

首先我们按开始时间对列表进行排序.

然后我们循环检查下一个开始时间是否低于上一个结束时间.

这将检查 x+1 是否与 x 重叠(而不是 x+2 是否与 x 重叠等)

间隔 = [[100,200],[150,250],[300,400]]intervalSorted = sorted(intervals, key=lambda x: x[0]) # 按开始时间排序对于范围内的 x(1,len(intervalsSorted)):如果 intervalSorted[x-1][1] >间隔排序[x][0]:打印{0} 与 {1} 重叠".format(intervals[x-1],intervals[x])# 结果:[100, 200] 与 [150, 250] 重叠

以下应该为您提供整个列表中的所有重叠部分.

间隔 = [[100,200],[150,250],[300,400],[250,500]]重叠 = [ [x,y] for x in interval for y in interval if x is not y and x[1]>y[0] and x[0]

请注意，这是一个 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"]]重叠 = [ [x,y] for x in interval for y in interval if x is not y and x[1]>y[0] and x[0]

I have a list of time entries (HHMM format) with a start time and a stop. I'm having trouble figuring out how to code it in Python where it returns if there's an overlap or not in the list.

Example

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

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

解决方案

First we sort the list by the start time.

Then we loop over it checking if the next start time is lower then the previous end time.

This will check if x+1 overlaps with x (not if x+2 overlaps with x, etc.)

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]

The following should give you all overlappings in the whole list.

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]

Note that this is a O(n*n) lookup. (anyone correct me here if I'm wrong!)

This is likely slower than the first (didn't test it, but I assume it is) because this iterates over the whole list for each single index. Should be similar to arbarnert's nested for loops example. But then again this does give you all the overlapping values as opposed to the first method I showed that only checked for overlapping times between those next to it (sorted by start time).

Extended test gives:

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

这篇关于检查时间跨度之间的重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！