假设我有很多由开始和结束时间戳标识的时间段。检测哪个周期重叠的最快方法是什么?
这里有一个例子:
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,J],[C,E],[C,I],[C,J],[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
如果有人能找到一个更快的方法来继续,那就太好了!每一毫秒对我来说都很宝贵呵呵 ;)
最佳答案
将所有时间一起排序,用它所属的段和开始/结束位标记每个时间。
然后,保留一个列表,说明您所在的分割市场(最初是空的)。
遍历时间列表。如果时间属于段 X,则如果它是开始时间,则将 X 添加到第二个列表。如果是结束时间,则从第二个列表中删除 X。在任何时候,第二个列表都会告诉您哪些段是重叠的。
如果有足够的segment来关心big-O,那么初始排序就是O(N Log N)。 迭代次数为 O(N)。
当然,不要指望 big-O 让你跑得快。仍然有不变的因素。 Here's how I do it.
关于algorithm - 检测重叠周期(或时间范围)的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47932320/