区间重合判断(C语言实现)

问题描述：

给定一个源区间[x,y](y>=x)和N个无序的目标区间[x1,y1],[x2,y2],[x3,y3],......[xN,yN],判断源区间[x,y]是不是在目标区间内？

例如给定源区间[1,6]和一组无序的目标区间[2,3],[1,2],[2,9],[3,4],即可认为区间[1,6]在区间[2,3],[1,2],[2,9],[3,4]内。

解决方法：

1.首先对无序的目标区间进行从小到大的排序；

2.对排好序的区间进行合并；

3.在合并后的区间中使用二分查找来判断给定源区间是否在被合并的这些互不相交的区间中的某一个包含。

#include 
#include 
#define MAX 100
struct Line
{int low;int high;
};
/*实现结构体数组的排序*/
void quicksort(struct Line a[],int l,int h)
{int i,j;struct Line t;i=l;j=h;t=a[l];while(it.low)j--;if(ii+1) quicksort(a,i+1,h);
}
/*对已经按照地位排好续的区间进行合并区间*/
int hebing(struct Line a[],int n)
{int i;int count=0;int lasthigh;lasthigh=a[0].high;for (i=1;i=a[i].low)  //当区间是相交时合并lasthigh=a[i].high;else  //当区间是相离是的情况，分别保存其中low和high{a[count++].high=lasthigh;a[count++].low=a[i].low;lasthigh=a[i].high;}}a[count++].high=lasthigh;  //保存最后的一个区间的高位return count;
}/*对合并以后的区间使用二分查找的方法查找源区间是否在目标区间上*/
void Search_souce(struct Line a[],int n,struct Line targt)
{int mid;int begin=0;int end=n;int flag=0;;while (begin<=end){mid=begin+(end-begin)/2;if (a[mid].low<=targt.low &&a[mid].high>=targt.high){flag=1;break;}else if (a[mid].low>=targt.high){end=mid-1;}else if (a[mid].high<=targt.low)end=mid+1;else {flag=0;break;}}if (1==flag)printf("yes\n");else printf("No\n");
}
int main()
{struct Line a[]={2,3,1,2,4,9,3,4};struct Line Lines[MAX]={0};struct Line targt={1,6};int count=0;int i;quicksort(a,0,3);count=hebing(a,4);Search_souce(a,count,targt);for (i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！