4.23 如何求两个有序集合的交集
【出自WY笔试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
有两个有序的集合，集合中的每个元素都是一段范围，求其交集，例如集合{[4，8]，[9，13]}和{[6，12]}的交集为{[6，8]，[9，12]}。
分析与解答：
方法一：蛮力法
最简单的方法就是遍历两个集合，针对集合中的每个元素判断是否有交集，如果有，则求出它们的交集，实现代码如下：
代码运行结果如下：
[6，8]
[9，12]
算法性能分析：
这种方法的时间复杂度为O（n^2）。
方法二：特征法
上述这种方法显然没有用到集合有序的特点，因此，它不是最佳的方法。假设两个集合为s1和s2。当前比较的集合为s1[i]和s2[j]，其中，i与j分别表示的是集合s1与s2的下标。可以分为如下几种情况：
1）s1集合的下界小于s2的上界：
S1[i] ____
S2[j] ____
在这种情况下，s1[i]和s2[j]显然没有交集，那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
2）s1的上界介于s2的下界与上界之间：
S1[i] ____
S2[j] ____
在这种情况下，s1[i]和s2[j]有交集（s2[j]的下界和s1[i]的上界），那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
3）s1包含s2：
S1[i] ____
S2[j] ____
在这种情况下，s1[i]和s2[j]有交集（交集为s2[j]），那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
4）s2包含s1：
S1[i] ____
S2[j] ____
在这种情况下，s1[i]和s2[j]有交集（交集为s1[i]），那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
5）s1的下界介于s2的下界与上界之间：
S1[i] ____
S2[j] ____
在这种情况下，s1[i]和s2[j]有交集（交集为s1[i]的下界和s2[j]的上界），那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
6）s2的上界小于s1的下界：
S1[i] ____
S2[j] ____
在这种情况下，s1[i]和s2[j]显然没有交集，那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
根据以上分析给出实现代码如下：
算法性能分析：
这种方法的时间复杂度为O（n1+n2），其中n1、n2分别为两个集合的大小。