重复区间问题

今天学习了一下重复区间问题

 

问题一，求最大重复区间个数

     1.数据是静态的：
        这个问题的最大重叠点一定出现在端点上。更进一步说，它一定可以出现在左端点上。
         对区间端点进行排序，N个区间排序后的端点数量为2N。
         遍历端点列表，左端点+1，右端点-1，记录遍历过程中的最大值，即为最大重复区间个数。
      2.数据是动态的：
          参考：算法导论中文版（原书第二版）190页思考题14-1
              http://bbs.csdn.net/topics/300181969

问题二，求最长重复区间长度

        首先还是将各行数据整理成x<y的标准形式，然后：

1)将各区间按照x从小到大排序（对于x(i)=x(i+1)这种情况可以优化，只保留较“长”的区间即可。比方说  此时有y(i)>y(i+1)，那我们只需要保留[x(i),y(i)]区间，而对[x(i+1),y(i+1)]可以省略）——这一步需要O(n*logn)；
2)将各区间数据进行整理，保持y严格递增，同时记录下被“删除”区间的最大长度max——这一步需要O(n)；
（例如对于[1,5][2,4][3,5][4,7][5,6]，为了保证y严格递增，需要删除某些区间，只剩下[1,5][4,7]
这一步的实际含义是统计区间相互“包含”的情况中，最长的“被包含”区间是多少）；
3)经过前两步之后，在剩下的区间序列中，不管x还是y都是保持严格递增的（从而保证剩下的区间中不会再出现相互“包含”的情况）。
此时最长的重叠区间只可能有相邻的两个区间产生，遍历统计并更新max——这一步需要O(n)
从而整体只需要O(n*logn)的复杂度，主要花费在排序上。
如果对于已经排好序的数据而言，O(n)线性时间内即可完成。