用什么算法,最快算出两个时间段的重叠部分呢

2015-07-19 23:38:45 +08:00
 meteor2013
任意两个时间序列:

比如
A: 3,4,5, 7,8,910, 18,19
B: 4,5, 16,17,18,19,20,

输出
4,5 18,19
8710 次点击
所在节点    程序员
41 条回复
zhengnanlee
2015-07-19 23:48:15 +08:00
最长公共子序列?
lixia625
2015-07-19 23:49:49 +08:00
print [i for i in B if i in A]
wy315700
2015-07-19 23:52:03 +08:00
线段树吧
aheadlead
2015-07-20 00:13:11 +08:00
随便找个查找树吧…
ariestiger
2015-07-20 00:15:36 +08:00
你这是有间断的两个时间序列,问题就不应该是你这样的。
本质上就是 Range 之间的交,差运算了。
之前做交易系统时,在订单发生退货退款时,要计算订单从下单到现在“真正”用了多少时间(也就是要把发生退货退款处理的时间段排队掉,而一个订单生命周期中可能发生多次退货退款,因为有的退货退款可能会被拒绝,用户后面可以继续申请退货退款),从而决定是不是要执行相应的定时任务。
因为 Java 里没有像 Ruby, Python 里的 Range 类,只能自己写个类来做一下了。
这个计算主要就是一个主线时间段,从订单最后更新时间到现在,另一个是若干退货退款的时间段(发生时间到结束时间),写个方法,循环,对每个退货退款时间段,看它和主线时间段的关系(其实主线时间段肯定是包含退货退款时间段的,不然就异常了),然后进行相减就行了。
你这里的话,主线时间段可以就用[min(A), max(A)],需要排队的支线时间段,从 A 和 B 中去提取,自己去考虑间隔点的问题了,然后做 Range 之间的运算就好了。
meteor2013
2015-07-20 00:16:00 +08:00
@zhengnanlee 不是最长公共子序列,是所有公共子序列
clink8001
2015-07-20 00:28:41 +08:00
用python 可以这么做:

a = [3,4,5, 7,8,910, 18,19 ]
b = [ 4,5, 16,17,18,19,20]
h = filter(lambda f: f in a, b)
print h
messyidea
2015-07-20 00:31:20 +08:00
线段树蛮方便的
iloahz
2015-07-20 00:35:29 +08:00
时间序列是不是可以认为可以有序啊,排好序两个指针跑一遍?
SoloCompany
2015-07-20 00:57:06 +08:00
题目没说清楚,那么久成了遍准求交集问题
set(A).retainAll(set(B)) 完事 ((
tushiner
2015-07-20 01:01:47 +08:00
看了九章算法的广告,只看标题以为楼主和他们是一路的
sciooga
2015-07-20 01:12:56 +08:00
有序的?
睡前随便想了一下 Python 应该是这样写比较快吧?

A = [3, 4, 5, 7, 8, 9, 10, 18, 19]
B = [4, 5, 16, 17, 18, 19, 20]
b_index = 0
b_end_index = len(B)
for i in A:
....while(b_index<b_end_index):
........if B[b_index] > i:
............break
........elif B[b_index] == i:
............print i
............break
........b_index += 1
meteor2013
2015-07-20 01:20:56 +08:00
@iloahz 对,是有序的
meteor2013
2015-07-20 01:23:38 +08:00
@messyidea
@wy315700

怎么个线段树?
msg7086
2015-07-20 01:47:58 +08:00
时间序列是什么?
时间点?
时间段?
题目好乱根本读不明白……
linxy
2015-07-20 01:48:50 +08:00
区间查找一般都是线段树。
meteor2013
2015-07-20 03:20:04 +08:00
@msg7086

A: 3,4,5, 7,8,9,10, 18,19 => A序列的子序列有3-5, 7-10和18-19
B: 4,5, 16,17,18,19,20,=> B有4-5,和 16-20两个子序列

=> A和B相同的重叠部分就是:4-5和 18-19两段。
msg7086
2015-07-20 03:29:00 +08:00
@meteor2013 性能好点的用线段树,性能差点的用归并比较。
我不懂前者。
mangocool
2015-07-20 08:58:25 +08:00
算法,咱不懂,学习!
messyidea
2015-07-20 09:04:14 +08:00
我感觉如果输入有序,且每个点都输入而不只输入时间段的起始和结束的话只需要扫一遍就可以了,复杂度O(2n), 如果是n个时间序列,要求覆盖m遍及以上的时间段,可以用线段树来处理。 说实话只有两个时间段用线段树小题大做了。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/206826

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX