3

给定开始时间和开始时间列表，我想知道列表是否包含重叠条目：

timesok = [('9:30', '10:00'), ('10:00', '10:30'), ('10:30', '11:00')]

wrongtimes1 = [('9:30', '10:00'), ('9:00', '10:30'), ('10:30', '11:00')]
wrongtimes2=[('9:30', '10:00'), ('10:00', '10:30'), ('9:15', '9:45')]

我从这个非常相似的问题中借用了一些代码来测试重叠的日期对：

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):

    r1 = Range(start=dt1_st, end=dt1_end)
    r2 = Range(start=dt2_st, end=dt2_end)
    latest_start = max(r1.start, r2.start)
    earliest_end = min(r1.end, r2.end)
    overlap = (earliest_end - latest_start)
    return overlap.seconds

我测试条目列表的功能：

def find_overlaps(times):
    pairs = list(combinations(times, 2))
    print pairs
    for pair in pairs:
        start1 = dt.strptime(pair[0][0], '%H:%M')
        end1 = dt.strptime(pair[0][1], '%H:%M')
        start2 = dt.strptime(pair[1][0], '%H:%M')
        end2 = dt.strptime(pair[1][1], '%H:%M')
        yield test_overlap(start1, end1, start2, end2) > 0

使用时，它的工作原理如下：

In [257]: list(find_overlaps(timesok))
[(('9:30', '10:00'), ('10:00', '10:30')), (('9:30', '10:00'), ('10:30', '11:00')), (('10:00', '10:30'), ('10:30', '11:00'))]
Out[257]: [False, False, False]

In [258]: list(find_overlaps(wrongtimes1))
[(('9:30', '10:00'), ('9:00', '10:30')), (('9:30', '10:00'), ('10:30', '11:00')), (('9:00', '10:30'), ('10:30', '11:00'))]
Out[258]: [True, False, False]

In [261]: list(find_overlaps(wrongtimes2))
[(('9:30', '10:00'), ('10:00', '10:30')), (('9:30', '10:00'), ('9:15', '9:45')), (('10:00', '10:30'), ('9:15', '9:45'))]
Out[261]: [False, True, False]

然而：

  1. 如果这对大型列表非常有效，我仍在争论自己。
  2. 我想知道是否有人可以提供更好的解决方案？
4

3 回答 3

1

我建议用这种方法来测试重叠，一种找到日期所有交集的方法：

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):
    return not (dt1_st < dt2_end and dt1_end >dt2_st)

这涵盖了重叠的所有可能性

于 2013-08-26T11:49:57.790 回答
0

这类似于区间重叠问题。详细阐述pkacprzak 的帖子。

按时间对事件列表进行排序。保留另一个活动元素列表。

像这样线性处理..

对于每个事件/元素..

  1. 如果起点，则添加到活动元素列表。
  2. 如果终点，则从活动元素列表中删除。
  3. 此外，在每个起点，当前活动元素与当前元素重叠。

另外，请查看其他此类间隔重叠的解决方案。就像这个一样。 如何有效地重叠区间

于 2013-08-26T12:35:00.113 回答
0

如果没有两对同时开始，您可以将时间戳视为“自午夜以来的分钟数”中的数值，然后按开始时间对输入列表进行排序，然后检查任何元素的结束时间是否大于开始时间下一个元素的时间：

from operator import itemgetter
from itertools import izip

def asNumber(s):
    colon = s.find(':')
    return int(s[:colon]) * 60 + int(s[colon+1:])

def isValid(l):
  numericPairs = [(asNumber(a), asNumber(b)) for (a,b) in l]
  sortedPairs = sorted(numericPairs, key=itemgetter(0))
  return all(startB >= endA for ((startA, endA), (startB, endB)) in izip(sortedPairs, sortedPairs[1:]))
于 2013-08-26T13:00:59.907 回答