重叠区间的问题

今日的笔试面试是有史以来最惨的一次，估计是被彻底鄙视了。
其中一道题目：

"
size_t           foo(unsigned       int       *a1,       size_t       al1,       unsigned       int*       a2,       size_t       al2)  
其中a1和a2都为无符号数组，al1和al2为数组的长度，数组的长度为偶数。  
无符号数组由一对数字区间组成。如下例：  
a1       为       0,1,3,6,10,20  
a2       为       0,1,20,50,4,5  
则       a1表示以下区间[0,1]       [3,6]       [10,20]  
            a2表示以下区间[0,1]       [20,50]       [4,5]  
则a1,a2的重叠部分为[0,1]       [4,5]，其长度为2  
函数foo要求返回重叠区间的长度。上例中为2.  

要求：  
            详细说明自己的解题思路，说明自己实现的一些关键点。  
写出函数foo原代码，另外效率尽量高，并给出代码的复杂性分析。  
限制：  
al1和al2的长度不超过100万。而且同一个数组的区间可能出现重重叠。  
            如a1可能为       0,5,           4,8,           9,100,           70,80  
            使用的存储空间尽量小。  
"

我能想出的只有两种：
一是Bitmap的算法：开一个4G/8=500MB的空间，将a1的元素映射进去，比如[1,3]就把1到3位都置为1。然后将a2对比得出重叠区间。但是需要500MB的额外空间，我觉得额外空间占用太多就没考虑这种方法；
二是先排序后遍历合并重叠空间的算法：这是我在试卷上的做法。空间小是很小，不过效率差一些。

面试的时候，面我的人还提示我说   “注意unsigned   int”和“观察数字的规律”，但是我摸不着头脑，不知道这第三种解法是什么，有谁可以指教一下。

 

 

先贴出贴子，回来再看看怎么解决...

 

 

题目源自：