检测重叠周期（或时间范围）的最快方法

Question

假设我通过开始和结束时间戳确定了很多时间段。什么是检测周期重叠的最快方法？

这是一个例子：

9个不同的句点，由起始（从）和结束（到）时间戳分隔。

A = [ from : 7s , to : 11s]
B = [ from : 1s, to : 8s]
C = [ from : 9s, to : 12s]
D = [ from : 4s, to : 7s]
E = [ from 10s, to: 15s]
F = [ from 0s, to : 5s]
G (oops i skipped it when drawing the image!)
H = [ from: 5s, to: 9s]
I = [ from: 11s, to: 13s]
J = [ from: 7s, to: 14s]

如何尽快检索所有重叠周期以获得以下结果？

[A，B]，[A，C]，[A，E]，[A，H]，[A，J]，[B，d]，[B，F]，[B，H]，[ B，d]，[C，E]，[C，I]，[C，d]，[d，F]，[d，H]，[d，J]，[E，I]，[E， J]，[H，J]，[I，J]]

JSFiddle of my own solution here

还有一个类似的jsfiddle，但这次是实时时间戳，从2017年1月到2017年3月美国东部时间上午8点到下午18点，还有很多。

JSFiddle with lots of timestamps

如果有人能找到更快捷的方式继续下去，那就太棒了！每毫秒对我来说是宝贵的呵呵;）

Answer 1

对所有时间进行排序，将每个时间标记为它所属的段，以及开始/结束位。

然后，保留一个列表，说明您所在的段（最初为空）。

迭代列表中的时间。如果时间属于段X，那么如果是开始时间，则将X添加到第二个列表。如果是结束时间，请从第二个列表中删除X.在任何时候，第二个列表都会告诉您哪些段重叠。

如果有足够的段来关注big-O，则初始排序为O（N Log N）。迭代是O（N）。

当然，不要指望大O让你快。仍有不变因素。 Here's how I do it.

Answer 2

蟒蛇：

from pprint import pprint as pp

intervals = [
    (7 , 11, 'A'),
    (1, 8, 'B'),
    (9, 12, 'C'),
    (4, 7, 'D'),
    (10, 15, 'E'),
    (0, 5, 'F'),
    (5, 9, 'H'),
    (11, 13, 'I'),
    (7, 14, 'J'),
]
intervals.sort()  # sort on interval start, then end if starts are equal
ans = []
for n0, (_, end0, name0) in enumerate(intervals[:-1]):
    for n1, (start1, _, name1) in enumerate(intervals[n0 + 1:]):
        if start1 < end0:
            ans.append(sorted((name0, name1)))
        else:
            break
pp(sorted(ans))

输出：

[['A', 'B'],
 ['A', 'C'],
 ['A', 'E'],
 ['A', 'H'],
 ['A', 'J'],
 ['B', 'D'],
 ['B', 'F'],
 ['B', 'H'],
 ['B', 'J'],
 ['C', 'E'],
 ['C', 'I'],
 ['C', 'J'],
 ['D', 'F'],
 ['D', 'H'],
 ['E', 'I'],
 ['E', 'J'],
 ['H', 'J'],
 ['I', 'J']]