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

[meteor2013]

任意两个时间序列：

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

输出
4,5 18,19

[zhengnanlee]

最长公共子序列？

[lixia625]

print [i for i in B if i in A]

[wy315700]

线段树吧

[aheadlead]

随便找个查找树吧…

[ariestiger]

你这是有间断的两个时间序列，问题就不应该是你这样的。
本质上就是 Range 之间的交，差运算了。
之前做交易系统时，在订单发生退货退款时，要计算订单从下单到现在“真正”用了多少时间（也就是要把发生退货退款处理的时间段排队掉，而一个订单生命周期中可能发生多次退货退款，因为有的退货退款可能会被拒绝，用户后面可以继续申请退货退款），从而决定是不是要执行相应的定时任务。
因为 Java 里没有像 Ruby, Python 里的 Range 类，只能自己写个类来做一下了。
这个计算主要就是一个主线时间段，从订单最后更新时间到现在，另一个是若干退货退款的时间段（发生时间到结束时间），写个方法，循环，对每个退货退款时间段，看它和主线时间段的关系（其实主线时间段肯定是包含退货退款时间段的，不然就异常了），然后进行相减就行了。
你这里的话，主线时间段可以就用[min(A), max(A)]，需要排队的支线时间段，从 A 和 B 中去提取，自己去考虑间隔点的问题了，然后做 Range 之间的运算就好了。

[meteor2013]

@zhengnanlee 不是最长公共子序列，是所有公共子序列

[clink8001]

用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]

线段树蛮方便的

[iloahz]

时间序列是不是可以认为可以有序啊，排好序两个指针跑一遍？

[SoloCompany]

题目没说清楚，那么久成了遍准求交集问题
set(A).retainAll(set(B)) 完事 （（

[tushiner]

看了九章算法的广告，只看标题以为楼主和他们是一路的

[sciooga]

有序的？
睡前随便想了一下 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]

@iloahz 对，是有序的

[meteor2013]

@messyidea
@wy315700

怎么个线段树？

[msg7086]

时间序列是什么？
时间点？
时间段？
题目好乱根本读不明白……

[linxy]

区间查找一般都是线段树。

[meteor2013]

@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]

@meteor2013 性能好点的用线段树，性能差点的用归并比较。
我不懂前者。

[mangocool]

算法，咱不懂，学习！

[messyidea]

我感觉如果输入有序，且每个点都输入而不只输入时间段的起始和结束的话只需要扫一遍就可以了，复杂度O(2n), 如果是n个时间序列，要求覆盖m遍及以上的时间段，可以用线段树来处理。 说实话只有两个时间段用线段树小题大做了。

[iker01]

一般用线段树解决区间问题。

[meteor2013]

@iker01 能举个例子具体说说吗？

[meteor2013]

@iker01 还有就是线段树一般处理无序序列，这个是有序的，能减少复杂度吗？

[likuku]

python

使用 set (集合) 类型一步搞定：

# & 交集
>>> print ( set([4, 5, 16, 17, 18, 19, 20]) & set([3, 4, 5, 7, 8, 9, 10, 18, 19]))
set([18, 19, 4, 5])

[RisingV]

就是求两个小整数数组交集，bitmap 足够快，O(m+n)

[meteor2013]

@likuku

集合好像感觉是找相同点的交集。
但是题目是要输出子序列。概念上略有不同。

@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两段。

[omph]

楼主表达能力堪忧，早该按 17 楼表达清楚
C++ 可以把 A 存到 map，key 是开始时间，val 是结束时间
使用 lower_bound，upper_bound 把 B 的开始和结束到 map 中定位（二分查找），两个定位的中间部分就是重叠部分
因 AB 有序，所以后续定位不用从头开始

[kzzhr]

区间树干这个是不是太重了。。
这好像是当年学hash的经典题型，题意不是很清楚。。

[meteor2013]

@omph
@kzzhr

二分查找听起来不错， 但如果A和B序列“非常非常大”，二分查找效率会不会不理想？
这时候用线段树有帮助吗？

[ant_sz]

先把两个序列都处理成 [start, end] 这样range 的序列，然后用两个指针指向两个range序列的头，依次后移两个指针来计算range的交。这应该是一个 O(M+N)的算法，我觉得应该比 O(M log N) 的 要好。

1. 如果 a 指向的 range 的结束时间 大于 b 指向的range 的开始时间，把 a 往后移动，反之亦然。
2. 如果 a 指向的 range 和 b 指向的 range 有交集，求交集并加入结果，然后将 a 和 b 结束时间较早的那个往后移动。

@meteor2013 另外，二分查找的性能其实是非常好的。A 和 B 序列非常大，最大能有多大呢？2^32 = 4G 个元素算不算大？然而用二分查找只需要 32 次迭代。二分查找的问题在于如果序列非常大，可能难以全部load到内存里，而且二分查找的时候有可能访问的内存位置跳跃比较大，因此可能需要频繁的置换虚拟内存。

线段树的查询也是需要 O(log N) 的时间的，而且你总要遍历其中一个序列所以时间复杂度综合来看也差不多 O(M log N) ，而且线段树的实现比较复杂，需要的内存空间大约是 O(2N) ，而且不一定有二分查找快，建树本身需要 O(N) 的时间复杂度。所以我觉得并不是一个好的方法。

[ffffwh]

从左到右linear scan，碰到开闭区间标记一下

[stackpop]

准确描述问题先吧。

根据你的描述，求的是离散的点的交集啊，数据是有序的，因而就是最长公共子序列啊。

如果说是很多个时间区间的集合，然后求哪些时间段有交叉，需要使用线段树。

[yuankui]

1. 两个序列排序
2. 两个指针指向两个序列
3. 谁小谁后移
4. 相等的话,就加入result_list,并且同时后移
5. 直到有一个指针到末尾

如果时间序列没有排序的话,这是个O(2*logN + N) = O(logN)的算法
如果有序的话,这是个O(N)的算法

[messyidea]

AB序列非常大的话可以进行一次预处理，先离散化数据。

[XadillaX]

线段树正解。

[KotiyaSanae]

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6449411

[KotiyaSanae]

……按错键发出去了。这篇paper前半部分讨论了几种（三种？）方法，找交集。里面有一个双堆法，个人感觉挺有意思。

[qwsqwa]

@yuankui 是正解。
楼主给的数据不是时间段，是时间点，只是几个时间点连起来就是时间段了。
如果给的是若干时间段，比如原问题中
A： 3,4,5, 7,8,910, 18,19
B: 4,5, 16,17,18,19,20
写成
A：3,5,7,10,18,19
B：4,5,16,20
的话才会用到线段树。

[qw7692336]

经过排序到数据？

[linxy]

@yuankui 这个好…

[kzzhr]

@meteor2013 所以我说hash嘛。区间数烧内存是小事，关键是需求没那么复杂，就比如现在让你找(1,n)的最大值，你也可以先排个序，问题是没有必要。奥对了，#33也给出了logn的解法，跟线段树时间一样，但是编码复杂度小很多。不过个人觉得还是hash优先。