Python中的时间范围重叠算法

我有一个包含不同 ID、开始日期和结束日期的列表， 让我们说：

[
(5, d.datetime(2010, 9, 19, 0, 0, 0),    d.datetime(2010, 9, 19, 0, 5, 10)),
(6, d.datetime(2010, 9, 19, 0, 0, 0),    d.datetime(2010, 9, 19, 12, 59, 59)),
(4, d.datetime(2010, 9, 19, 10, 30, 17), d.datetime(2010, 9, 19, 20, 20, 59)),
(6, d.datetime(2010, 9, 19, 14, 12, 0),  d.datetime(2010, 9, 19, 23, 59, 59)),
(5, d.datetime(2010, 9, 19, 17, 0, 22),  d.datetime(2010, 9, 19, 19, 14, 20))
]

我需要以某种方式找到重叠的时间范围，并准备具有在特定时间范围内覆盖的正确 ID 的新列表，例如上面的列表结果应该是：

[
('5,6',   d.datetime(2010, 9, 19, 0, 0, 0),    d.datetime(2010, 9, 19, 0, 5, 10),
('6',     d.datetime(2010, 9, 19, 0, 5, 10),   d.datetime(2010, 9, 19, 10, 30, 17),
('4,6',   d.datetime(2010, 9, 19, 10, 30, 17), d.datetime(2010, 9, 19, 12, 59, 59),
('4',     d.datetime(2010, 9, 19, 12, 59, 59), d.datetime(2010, 9, 19, 14, 12, 0),
('4,6',   d.datetime(2010, 9, 19, 14, 12, 0),  d.datetime(2010, 9, 19, 17, 0, 22),
('4,5,6', d.datetime(2010, 9, 19, 17, 0, 22),  d.datetime(2010, 9, 19, 19, 14, 20),
('4,6',   d.datetime(2010, 9, 19, 19, 14, 20), d.datetime(2010, 9, 19, 20, 20, 59),
('6',     d.datetime(2010, 9, 19, 20, 20, 59), d.datetime(2010, 9, 19, 23, 59, 59)
]

视觉概念：

实际上现在我有这样的解决方案：我正在获取整个范围的最小和最大日期，然后开始每 1 秒从 min_date 到 max_date 迭代，特别是当我们匹配目标列表中的一些间隔时，我保存匹配的ids 作为字典键，并将迭代器中的时间作为值附加到列表，然后将其保存到父列表，然后是下一个和下一个。最后，我检查父列表中的所有字典，并将 ids 作为键，将值列表中的第一个、最后一个日期作为我需要查找的范围。 但是当我以月份为单位计算范围时，这个解决方案的工作速度非常慢。因为以秒为单位迭代 1 个月需要太多时间。

这是代码：

    def delta(start, end, delta):
        cur = start
        while cur < end:
            yield cur
            cur += delta

    final_ranges = []
    last_result = None
    i = -1
    for checker_date in delta(
            sorted_ranges_by_start[0]['start'],
            sorted_ranges_by_end[-1]['end'],
            relativedelta(seconds=1)):

        aggregator = []
        for rng in ranges:
            if rng['start'] <= checker_date <= rng['end']:
                aggregator.append(str(rng['id']))

        if len(aggregator) > 0:
            ids = ','.join(set(aggregator))
            if last_result != ids:
                final_ranges.append({})
                last_result = ids
                i += 1

            if ids not in final_ranges[i]:
                final_ranges[i][ids] = []

            final_ranges[i][ids].append(checker_date)

但正如我所说，它在大范围内运行速度非常慢。

通过这种方式，请帮助我找到不需要迭代一个月就能完成的算法，或者建议任何提高迭代速度的方法（不确定，也许尝试在 C 上编写这部分，然后嵌入到 Python 中）

Thanks.

为每个间隔创建两条记录：{id, time, start/end}

按时间比较的所有这些记录的排序列表。如果时间字段相同，请比较开始/结束字段并首先选择结束。

浏览一下列表。

当遇到开始记录时，添加id到active list， 找时间last time

当遇到结束记录时，输出active list with last time标签到结果，然后从活动列表中删除 id。改变last time

让我们有间隔

 A: 0..3
 B: 1..2
 C: 2..4

Records:

 (A,0,s), (A,3,e), (B,1,s), (B,2,e), (C,2,s), (C,4,e)

Sorted:

 (A,0,s), (B,1,s), (B,2,e), (C,2,s), (A,3,e), (C,4,e)

步行排序列表：

  current      active      output         last time
  (A,0,s)      A            -              0           
  (B,1,s)      A,B        A 0..1           1
  (B,2,e)      A          A,B 1..2         2
  (C,2,s)      A,C          -              2
  (A,3,e)      C          A,C  2..3        3
  (C,4,e)      -          C 3..4           4