检查两个时间间隔是否重叠

Question

检查两个时间间隔是否重叠

4

我有两组不同的时间间隔集合：

Intervals1:
{'ending_time': '2016-02-26 07:10:40.276504', 'starting_time': '2016-02-26 07:10:39.286168'}
{'ending_time': '2016-02-26 07:10:40.722193', 'starting_time': '2016-02-26 07:10:40.301116'}
{'ending_time': '2016-02-26 07:10:41.329731', 'starting_time': '2016-02-26 07:10:40.812676'}
{'ending_time': '2016-02-26 07:10:42.146669', 'starting_time': '2016-02-26 07:10:41.419473'}
{'ending_time': '2016-02-26 07:10:42.413005', 'starting_time': '2016-02-26 07:10:42.203540'}
{'ending_time': '2016-02-26 07:10:42.686456', 'starting_time': '2016-02-26 07:10:42.442964'}
{'ending_time': '2016-02-26 07:10:43.198191', 'starting_time': '2016-02-26 07:10:42.746994'}
{'ending_time': '2016-02-26 07:10:44.502593', 'starting_time': '2016-02-26 07:10:43.288611'}
{'ending_time': '2016-02-26 07:10:46.525823', 'starting_time': '2016-02-26 07:10:44.709627'}
{'ending_time': '2016-02-26 07:10:47.098280', 'starting_time': '2016-02-26 07:10:46.886541'}
--------------------------
Interval2:
{'ending_time': '2016-02-26 07:10:41.482954', 'starting_time': '2016-02-26 07:10:39.590220'}
{'ending_time': '2016-02-26 07:10:42.615738', 'starting_time': '2016-02-26 07:10:41.649375'}
{'ending_time': '2016-02-26 07:10:46.365902', 'starting_time': '2016-02-26 07:10:45.987907'}
{'ending_time': '2016-02-26 07:10:47.698375', 'starting_time': '2016-02-26 07:10:46.510641'}

我使用以下代码将这些日期时间字符串转换为真正的日期时间对象：

datetime.datetime.strptime(dictionary['starting_time'], "%Y-%m-%d %H:%M:%S.%f")

我在这里尝试通过比较两个不同集合来匹配重叠的时间间隔。

例如：Intervals1[0] 和 Intervals2[0] 重叠，但 Intervals1[7] 和 Intervals2[0] 不重叠。

那么，正确的方法是什么？简要说明就足够了。

- mertyildiran

似乎这些值是表示日期/时间的字符串并不相关。如果您使用带有元组的列表，问题仍将保持不变：L1 = [(1, 10), (100, 120)]，L2 = [(9, 15), (50, 60)] - 这里 L1[0] 和 L2[0] 重叠。相关链接：合并重叠区间和 Python - 删除重叠列表。 - jfs

4个回答

1

您可以像这样比较范围：

timerange1 = {'ending_time': '2016-02-26 07:10:40.276504', 'starting_time': '2016-02-26 07:10:39.286168'}
timerange2 = {'ending_time': '2016-02-26 07:10:41.482954', 'starting_time': '2016-02-26 07:10:39.590220'}

# use a function to make this 'interval' data structure (instead of me being lazy)
interval1 = [datetime.datetime.strptime(timerange1['starting_time'], "%Y-%m-%d %H:%M:%S.%f")]
             datetime.datetime.strptime(timerange1['ending_time'], "%Y-%m-%d %H:%M:%S.%f")]
interval2 = [datetime.datetime.strptime(timerange2['starting_time'], "%Y-%m-%d %H:%M:%S.%f")]
             datetime.datetime.strptime(timerange2['ending_time'], "%Y-%m-%d %H:%M:%S.%f")]

def overlaps(interval1, interval2):
    results = []
    for timestamp in interval1:
        results.append(interval2[0] < timestamp < interval2[1])
    for timestamp in interval2:
        results.append(interval1[0] < timestamp < interval1[1])
    return True in results

- willnx

你使用列表中间步骤的原因是什么？ - Tadhg McDonald-Jensen

要完整地检查时间戳是否落在任何时间间隔内。时间间隔1的开始/结束时间可能不在时间间隔2之间，但时间间隔1更“宽”，因此时间间隔2的开始/结束时间可能会落在时间间隔1之间。明白吗？ - willnx

不，我会编辑您的帖子并展示我如何做，您不必接受。 - Tadhg McDonald-Jensen

好的，我会在我的回答中添加更多的上下文来解释为什么我使用了列表。 - willnx

好的，我建议了一下，我只是真正地将 for timestamp in interval1 改为了 for timestamp in interval1.values()，并将 interval2[0] 改为了 interval2['starting_time']，以及相应的更改，以便将它们用作字典而不是列表。 - Tadhg McDonald-Jensen

1

哦！我以为你指的是“重叠”函数中的“结果”列表，而不是我将提问者的字典转换为列表。我只是在本地运行它时这样做，以便更轻松地复制/粘贴。对此很抱歉。 - willnx

1

相比于4mn，以下内容仅需要2mn次比较，其中m表示Intervals1中的记录数，n表示Intervals2中的记录数。

Intervals1 = [
    {'ending_time': '2016-02-26 07:10:40.276504', 'starting_time': '2016-02-26 07:10:39.286168'},
    {'ending_time': '2016-02-26 07:10:40.722193', 'starting_time': '2016-02-26 07:10:40.301116'},
    {'ending_time': '2016-02-26 07:10:41.329731', 'starting_time': '2016-02-26 07:10:40.812676'},
    {'ending_time': '2016-02-26 07:10:42.146669', 'starting_time': '2016-02-26 07:10:41.419473'},
    {'ending_time': '2016-02-26 07:10:42.413005', 'starting_time': '2016-02-26 07:10:42.203540'},
    {'ending_time': '2016-02-26 07:10:42.686456', 'starting_time': '2016-02-26 07:10:42.442964'},
    {'ending_time': '2016-02-26 07:10:43.198191', 'starting_time': '2016-02-26 07:10:42.746994'},
    {'ending_time': '2016-02-26 07:10:44.502593', 'starting_time': '2016-02-26 07:10:43.288611'},
    {'ending_time': '2016-02-26 07:10:46.525823', 'starting_time': '2016-02-26 07:10:44.709627'},
    {'ending_time': '2016-02-26 07:10:47.098280', 'starting_time': '2016-02-26 07:10:46.886541'}
    ]
Intervals2 = [
    {'ending_time': '2016-02-26 07:10:41.482954', 'starting_time': '2016-02-26 07:10:39.590220'},
    {'ending_time': '2016-02-26 07:10:42.615738', 'starting_time': '2016-02-26 07:10:41.649375'},
    {'ending_time': '2016-02-26 07:10:46.365902', 'starting_time': '2016-02-26 07:10:45.987907'},
    {'ending_time': '2016-02-26 07:10:47.698375', 'starting_time': '2016-02-26 07:10:46.510641'}
    ]

for i1, d1 in enumerate(Intervals1):
  for i2, d2 in enumerate(Intervals2):
    start1 = d1["starting_time"]
    start2 = d2["starting_time"]
    end1 = d1["ending_time"]
    end2 = d2["ending_time"]

    if end1 >= start2 and end2 >= start1:
        print("Intervals1", i1, "overlaps with Intervals2", i2)

- K.Marker

1

很简短。从同事那里得到的，不知道作者)))

def is_overlapped(ranges):
    sorted_ranges = sorted(ranges, key=lambda begin_end: begin_end[0])
    return list(chain(*sorted_ranges)) != sorted(chain(*sorted_ranges))

##################################################################

没有重叠部分：

print(is_overlapped([ (datetime(2023年, 10月, 1日), datetime(2023年, 12月, 31日)), (datetime(2020年, 11月, 1日), datetime(2020年, 12月, 2日)) ]))

False

第一步第二步：

打印(is_overlapped([ (datetime(2013年10月1日), datetime(2013年12月31日)), (datetime(2000年11月1日), datetime(2020年12月2日)) ]))

请注意，这是机器翻译的结果，可能不太准确。

True

第一步在第二步之后：

打印(is_overlapped([ (datetime(2013年10月1日), datetime(2023年12月31日)), (datetime(2020年11月1日), datetime(2020年12月2日)) ]))

True

第一步变成第二步：

打印(is_overlapped([ (datetime(2010, 10, 1), datetime(2013, 12, 31)), (datetime(2013, 11, 1), datetime(2015, 12, 2)) ]))

True

第二次更改为第一次：

打印（is_overlapped（[（datetime（2011，10，1），datetime（2013，12，31）），（datetime（2010，11，1），datetime（2011，12，2））] ））

True

- Anton Makarov

2

对于其他人：这个方法可行 - 但是还需要 from itertools import chain。 - Tyler Chong

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tadhg McDonald-Jensen · Accepted Answer

datetime对象支持比较，因此您只需要检查第一个开始时间是否在另一个时间段的开始和结束之间，或者第一个结束时间是否在另一个时间段的开始和结束之间，或者反之。

def overlap(first_inter,second_inter):
    for f,s in ((first_inter,second_inter), (second_inter,first_inter)):
        #will check both ways
        for time in (f["starting_time"], f["ending_time"]):
            if s["starting_time"] < time < s["ending_time"]:
                return True
    else:
        return False

编辑：还要注意的是，由于您的日期字符串格式中最重要的值首先出现，因此它可以很容易地进行比较，而不必将其转换为datetime对象。

编辑2：以下是一份记录所有组合及其结果到字典中的示例：

import itertools

combos = {(i1,i2):overlap(int1,int2)
             for (i1,int1),(i2,int2)
                in itertools.product(enumerate(Intervals1),enumerate(Intervals2))}

print(*combos.items(),sep="\n")

这样，combos[0,1] 将与 Intervals[0] 和 Intervals[1] 相互重叠，以此类推。

然后，要获取一组重叠时间，您可以使用：

overlapped = set(com for com,was_overlapped in combos.items() if was_overlapped)

最后编辑：我很抱歉使用了非常长的dict comprehension，混乱的格式使得处理数据非常困难，如果原始时间列表有规律，那么只使用字典推导的for循环部分就能得到所需结果：

for (i1,int1),(i2,int2) in itertools.product(enumerate(Intervals1),enumerate(Intervals2)):
    if overlap(int1,int2):
        print(i1,i2)

或者，要对 overlapped 集合进行排序，您可以使用内置的 sorted 函数：

overlapped = sorted(overlapped) #this gives a list