5

我有一个时间条目列表（HHMM 格式），其中包含开始时间和停止时间。我无法弄清楚如何在 Python 中对其进行编码，如果列表中有重叠，它会返回哪里。

例子

条目 1：1030、1245；
条目 2：1115、1300
== 真

条目 1：0900、1030；
条目 2：1215、1400
== 错误
4

5 回答 5

11

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

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

这将检查 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']
于 2013-02-14T22:44:08.400 回答
2

为了将来参考，@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])

此外，间隔树可用于此类问题。

于 2013-12-03T21:55:35.377 回答
1

要扩展@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']
于 2017-08-01T15:04:11.690 回答
0

假设你有一个intervals_overlap(interval1, interval2)函数……</p>

第一个想法是对列表中的每一对间隔进行简单的迭代：

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

但是你应该能够找出更聪明的方法来解决这个问题。

于 2013-02-14T22:31:41.730 回答
-1

简单的方法：

我将数字更改为字符串，因为条目 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
于 2014-11-30T06:33:36.610 回答