题目： 给定一个目标区间[x,y]和N个无序的源区间[x1,y1] [x2,y2] ... [xn,yn]，判断源区间[x,y]是不是在目标区间内。
思路：把源区间按x从小到大排序，再把区间依次合并，每完整得到一个合并区间后，判断[x,y]是否在合并区间内。
#include <stdio.h> #include <stdlib.h> typedef struct { int x; int y; }Region; int cmp(const void * a, const void * b) //由小到大排序 { return *(int *)a - *(int *)b; } bool isInRegion(Region dst, Region * src, int N) { qsort(src, N, sizeof(src[0]), cmp); //按输入的x 从小到大排序 Region currentRegion = src[0]; for(int i = 1; i < N; i++) { if(src[i].y <= currentRegion.y) //判断的区间已经包含在当前区间 { continue; } else { if(src[i].x > currentRegion.y) //出现了新的区间 与当前区间不交叠 { if(dst.x >= currentRegion.x && dst.y <= currentRegion.y) //若目标区间在已经截断的区间内 返回true { return true; } else //否则 把当前区间改成新出现的区间 { currentRegion = src[i]; } } else { currentRegion.y = src[i].y; } } } if(dst.x >= currentRegion.x && dst.y <= currentRegion.y) //若目标区间在已经截断的区间内 返回true { return true; } else { return false; } } int main() { Region src[3] = {{2,3},{1,2},{4,9}}; Region dst = {1,6}; bool b = isInRegion(dst, src, 3); return 0; }
看网上别人的答案。http://blog.csdn.net/tianshuai1111/article/details/7828961中的思路
先用区间的左边界值对目标区间进行排序O(nlogn)，对排好序的区间进行合并O(n)，对每次待查找的源区间，用二分查出其左右两边界点分别处于合并后的哪个源区间中O(logn)，若属于同一个源区间则说明其在目标区间中，否则就说明不在。
感觉这个解法中虽然说查找处于合并后的哪个区间只要O（logn）但是必须要先把所有的区间合并完。我的方法虽然要对每一个合并区间判断，但是如果中间就找到了后面就不用做了。
#include <iostream> #include <algorithm> using namespace std; struct Line { int low, high; bool operator<(const Line &l) const {return low<l.low;} }; #define MAXN 10001 Line lines[MAXN]; // 目标区间 int ncnt = 0; // 合并后区间的个数 #define N 101 Line sl[N]; // 待查询的源区间 // 用二分查找找出key所在的区间，以区间的low作为划分 int GetIndex(int key) { int u, v; u = 0; v = ncnt-1; while (u<=v) // u,v可取等号 { int m = (u+v)>>1; if (key >= lines[m].low) u = m+1; else v = m-1; } return v; } int main() { int n, k, i, j; cin >> n >> k; // n是目标区间的个数,k是待查询的源区间的个数 for (i=0; i<n; i++) cin >> lines[i].low >> lines[i].high; for (i=0; i<k; i++) cin >> sl[i].low >> sl[i].high; // 排序O(nlogn) sort(lines, lines+n); // 合并O(n) int lasthigh = lines[0].high; for (i=1; i<n; i++) if (lasthigh >= lines[i].low) lasthigh = lines[i].high; else { lines[ncnt++].high = lasthigh; lines[ncnt].low = lines[i].low; lasthigh = lines[i].high; } lines[ncnt++].high = lasthigh; for (i=0; i<k; i++) { // 单词查找时间O(logn) int s1 = GetIndex(sl[i].low); int s2 = GetIndex(sl[i].high); if (s1==s2 && sl[i].high <= lines[s2].high) printf("Yes\n"); else printf("No\n"); } }
法二：使用并查集，对每个区间合并到一个子树上，最后判断源区间的x和y的根是否相同。
----------------------------------------------------------------------------------------------
补充并查集知识：
#include<iostream> using namespace std; const int size = 100; int father[size]; int rank[size]; void make_set(int n) { for(int i = 1; i <= n; i ++){ father[i] = i; rank[i] = 1; } } int find_set(int x)//寻找代表元素 { if(x != father[x]){ //元素不是单独的段，在某个区间内，返回某个区间代表 father[x] = find_set(father[x]); } return father[x]; } void Union(int x, int y) { x = find_set(x); y = find_set(y); if(x == y){ //两个在同一个区间 return ; } if(rank[x] < rank[y]){ father[x] = y; } else{ father[y] = x; if(rank[x] == rank[y]){ rank[x] ++; } } } int main() { int x1, y1; cin >> x1 >> y1;//输入要判断区间 int x, y; int n; cin >> n; //区间的个数 make_set(size); while(n --){ cin >> x >> y; //输入每个区间 if(x > y){//这一步很关键，表示考虑的周到 swap(x, y); } for(int i = x + 1; i <= y; i++){//将区间内的 段合并到已有区间 Union(x, i); } } if(find_set(x1) == find_set(y1)){ cout << "yes" << endl; } else{ cout << "no" << endl; } system("pause"); }
这道题后面还有个二维区间重合判断的，说是要用到线段树。还没看完，之后单独写吧。
原文：http://www.cnblogs.com/dplearning/p/4094930.html