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

[meteor2013]

任意两个时间序列：

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

输出
4,5 18,19

[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 这个好…