编程之美区间重合判断
一，问题：
1. 给定一个源区间[x,y]和N个无序的目标区间[x1,y1] [x2,y2] ... [xn,yn]，判断源区间[x,y]是不是在目标区间内。
2. 给定一个窗口区域和系统界面上的N个窗口，判断这个窗口区域是否被已有的窗口覆盖。
方法一：编程之美的解法，首先利用快排将区间按照从小到大排序，[2,3][1,2][3,9]-》[1,2][2,3][3,9]；然后对排序的区间进行合并；合并后运用二分法查找。
#include <iostream>using namespace std;const int size = 100;int faher[size];//我们用正负区分根节点//负表示根节点，负数表示集合中的个数//正数表示子节点，father[i]表示父亲的索引void MakeSet(int len)//-1表示集合中的个数为1{for(int i=0; i<len; i++){faher[i] = -1;//初识化，大家独自一个集体}}int Find(int x){if(faher[x]>=0)return Find(faher[x]);elsereturn x;}void Union(int x,int y){int xRoot = Find(x);int yRoot = Find(y);int temp;if(xRoot != yRoot){ temp = faher[xRoot] + faher[yRoot];if(faher[xRoot]<faher[yRoot]){//说明x的子节点多余y的子节点，避免生产退化树faher[xRoot] = temp;faher[yRoot] = xRoot;}else{faher[yRoot] = temp;faher[xRoot] = yRoot;}}}void PrintSet(int len){cout<<"Set:";for(int i=0; i<len; i++)cout<<faher[i]<<" ";cout<<endl;}int main(){ int n;cin>>n; //区间的个数 MakeSet(20);PrintSet(20);while(n--){ int x,y;cin>>x>>y; //输入每个区间 if(x>y){//这一步很关键，表示考虑的周到 swap(x, y); } for(int i=x+1; i<=y; i++){//将区间内的 段合并到已有区间 Union(x,i); } PrintSet(20);} int x1, y1; cin>>x1>>y1;//输入要判断区间 if(Find(x1) == Find(y1)){ cout<<"yes"<<endl; } else{ cout<<"no"<<endl; } system("pause"); return 0;}例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为[10 12]，其大小为3；行(20 10)和（20 30）的重叠区间大小为1。
答案：解法1先排序+判断重复的区间http://www.cnblogs.com/absolute8511/archive/2009/05/13/1649584.html
解法2：用位图，int bitmap[len]，对将每个区间写入位图，位图相应位置加1操作，bitmap[pos]++，最后统计大于的区域且连续的区域的长度最大值。就向下图所示，区域的计数为1表示有但是没有重叠，0表示该区间没有被覆盖到，2表示有个区间覆盖到，3表示有3个区间覆盖到，4表示有4个区间覆盖到。我们只有判断大于1区域长度的最大值，下图中明显为4区域。
________________________________________________________________________
|______1_____|______2______|____3____|____0____|_______4_________________|