每日一题（21）――区间重合检测（一）（普通区间合并&并查集） - 小熊不去实验室 - 博客频道 - CSDN.NET

给定一个源区间[x,y]和N个无序的目标区间[x1,y1] [x2,y2] ... [xn,yn]，判断源区间[x,y]是不是在目标区间内

解法1：

先用区间的左边界值对目标区间进行排序O(nlogn)，对排好序的区间进行合并O(n)，对每次待查找的源区间，二分法查出其左右两边界点分别处于合并后的哪个源区间中O(logn)，若属于同一个源区间则说明其在目标区间中，否则就说明不在。

1. struct region  
2. {
3.     int start;  
4.     int over;  
5.     bool operator<(const region& r) const  
6.     {return start<r.start;}  
7. };  
8. //binary-research by merged[].start to find the most nearly merged[].start  
9. int check(region m[],int length,int testId)  
10. {  
11.     int low=0,high=length+1;  
12.     int mid;  
13.     while(low<=high)  
14.     {  
15.         mid=(low+((high-low)>>1));  
16.         if(m[mid].start <= testId) low=mid+1;  
17.         else  
18.             high=mid-1;  
19.     }  
20.     return high;//返回的是high值，此时high小于等于mid,小于low;  
21. }  
22. int main()  
23. {  
24.     region r[30],merged[30],test;  
25.     int n;//count of array  
26.     int m;//conut of merged array  
27.     cin>>n;  
28.     for(int i=0; i<n; i++)  
29.         cin>>r[i].start>>r[i].over;  
30.     cin>>test.start>>test.over;  
31.   
32.     sort(r,r+n);//sort by start time  
33.     cout<<endl;  
34.     cout<<"Sorted Region: "<<endl;  
35.     for(int i=0;i<n;i++) cout<<r[i].start<<" "<<r[i].over<<endl;  
36.     cout<<endl;  
37.     //mergeRegions;  
38.     m=0;  
39.     int lasthigh = r[0].over;  
40.     merged[0].start = r[0].start;  
41.     merged[0].over = r[0].over;  
42.     for (int i=1; i<n; i++)  
43.     {  
44.         if (lasthigh >= r[i].start)//注意：>= 合并操作  
45.         {  
46.             lasthigh = lasthigh>r[i].over?lasthigh:r[i].over;//lasthigh等于较大值  
47.             merged[m].over = lasthigh;  
48.         }  
49.         else //扩展一个新的区间  
50.         {  
51.             m++;  
52.             merged[m].start = r[i].start;  
53.             merged[m].over = r[i].over;  
54.             lasthigh = r[i].over;  
55.         }  
56.     }  
57.     cout<<"Merged Region: "<<endl;  
58.     for(int i=0;i<=m;i++) cout<<merged[i].start<<" "<<merged[i].over<<endl;  
59.     cout<<endl;  
60.     //check the test line binary-research  
61.     int startId = check(merged, m, test.start);  
62.     int overId = check(merged, m, test.over);  
63.     if(startId==overId && test.over<=merged[overId].over)  
64.         cout<<"OK! The test line is in the set."<<endl;  
65.     else  
66.         cout<<"False! The test line is not in the set."<<endl;  
67. } 

解法2：

利用并查集，首先初始化每个元素的代表节点father[i]=i等于其本身，count[i]=1;然后每输入一个区间，合并一次（遍历区间内的每一个元素，更新其代表）；最后查询待查区间的首位两个元素是否在同一区间内。这种方法将区间转化为离散的集合，操作容易，但是浪费空间比较严重，对于大规模的区间不太实用。

1. int father[SIZE];  
2. int count[SIZE];  
3.   
4. void initail(int num)  
5. {  
6.     for (int i=0; i<num; i++)  
7.     {  
8.         father[i]=i;//每个集合的代表是自己  
9.         count[i]=1; //代表一个元素  
10.     }  
11. }  
12.   
13. void merge(int x, int y)  
14. {  
15.     if(father[x]==father[y])  
16.         return;  
17.     else  
18.     {  
19.         if(count[x]>=count[y])  
20.         {  
21.             father[y]=father[x];  
22.         }  
23.         else  
24.             father[x]=father[y];   
25.         count[father[x]]++;  
26.     }  
27. }  
28. int main()  
29. {  
30.     memset(father,-1,sizeof(father));  
31.     memset(count,1,sizeof(count));  
32.     int n,t0,t1;  
33.     cin>>n;  
34.     initail(SIZE);//需要初始化整个可能的区间  
35.     while(n--)  
36.     {  
37.         cin>>t0>>t1;  
38.         if(t0>t1)  
39.             swap(t0,t1);  
40.         for(int i=t0+1; i<=t1; i++)  
41.             merge(t0,i);  
42.     }  
43.     int test0,test1;  
44.     cin>>test0>>test1;  
45.   
46.     if(father[test0]==father[test1])  
47.         cout<<"Yes"<<endl;  
48.     else  
49.         cout<<"No"<<endl;  
50. }

Read full article from 每日一题（21）――区间重合检测（一）（普通区间合并&并查集） - 小熊不去实验室 - 博客频道 - CSDN.NET