一、问题:
给定一个源区间[x,y]和N个无序的目标区间[x1,y1] [x2,y2] ... [xn,yn],判断源区间[x,y]是不是在目标区间内。
Input:
6
20 25
0 10
15 20
40 45
30 40
50 60
20 22
Output:
//解法1
Sorted Region:
0 10
15 20
20 25
30 40
40 45
50 60
Merged Region:
0 10
15 25
30 45
50 60
OK! The test line is in the set.
//解法2
Yes
二、解法:
解法1:
先用区间的左边界值对目标区间进行排序O(nlogn),对排好序的区间进行合并O(n),对每次待查找的源区间,二分法查出其左右两边界点分别处于合并后的哪个源区间中O(logn),若属于同一个源区间则说明其在目标区间中,否则就说明不在。
#include <iostream> #include <algorithm> using namespace std; struct region { int start; int over; bool operator<(const region& r) const {return start<r.start;} }; //binary-research by merged[].start to find the most nearly merged[].start int check(region m[],int length,int testId) { int low=0,high=length+1; int mid; while(low<=high) { mid=(low+((high-low)>>1)); if(m[mid].start <= testId) low=mid+1; else high=mid-1; } return high;//返回的是high值,此时high小于等于mid,小于low; } int main() { region r[30],merged[30],test; int n;//count of array int m;//conut of merged array cin>>n; for(int i=0; i<n; i++) cin>>r[i].start>>r[i].over; cin>>test.start>>test.over; sort(r,r+n);//sort by start time cout<<endl; cout<<"Sorted Region: "<<endl; for(int i=0;i<n;i++) cout<<r[i].start<<" "<<r[i].over<<endl; cout<<endl; //mergeRegions; m=0; int lasthigh = r[0].over; merged[0].start = r[0].start; merged[0].over = r[0].over; for (int i=1; i<n; i++) { if (lasthigh >= r[i].start)//注意:>= 合并操作 { lasthigh = lasthigh>r[i].over?lasthigh:r[i].over;//lasthigh等于较大值 merged[m].over = lasthigh; } else //扩展一个新的区间 { m++; merged[m].start = r[i].start; merged[m].over = r[i].over; lasthigh = r[i].over; } } cout<<"Merged Region: "<<endl; for(int i=0;i<=m;i++) cout<<merged[i].start<<" "<<merged[i].over<<endl; cout<<endl; //check the test line binary-research int startId = check(merged, m, test.start); int overId = check(merged, m, test.over); if(startId==overId && test.over<=merged[overId].over) cout<<"OK! The test line is in the set."<<endl; else cout<<"False! The test line is not in the set."<<endl; }
解法2:
利用并查集,首先初始化每个元素的代表节点father[i]=i等于其本身,count[i]=1;然后每输入一个区间,合并一次(遍历区间内的每一个元素,更新其代表);最后查询待查区间的首位两个元素是否在同一区间内。这种方法将区间转化为离散的集合,操作容易,但是浪费空间比较严重,对于大规模的区间不太实用。
#include <iostream> #define SIZE 100 using namespace std; int father[SIZE]; int count[SIZE]; void initail(int num) { for (int i=0; i<num; i++) { father[i]=i;//每个集合的代表是自己 count[i]=1; //代表一个元素 } } void merge(int x, int y) { if(father[x]==father[y]) return; else { if(count[x]>=count[y]) { father[y]=father[x]; } else father[x]=father[y]; count[father[x]]++; } } int main() { memset(father,-1,sizeof(father)); memset(count,1,sizeof(count)); int n,t0,t1; cin>>n; initail(SIZE);//需要初始化整个可能的区间 while(n--) { cin>>t0>>t1; if(t0>t1) swap(t0,t1); for(int i=t0+1; i<=t1; i++) merge(t0,i); } int test0,test1; cin>>test0>>test1; if(father[test0]==father[test1]) cout<<"Yes"<<endl; else cout<<"No"<<endl; }
这道题每日一题(20)——高效安排见面会最后一部分的扩展问题一有相似之处,那道题是求重合层数。这道题是求是否重合。