区间重合判断（pojg校门外的树）

pojg；http://poj.grids.cn/practice/2808

解法1：以空间换时间：

#include<stdio.h>
#include<string.h>
int main()
{
    int L,M;
    scanf("%d%d",&L,&M);
    bool *a=new bool[10001];
    memset(a,1,sizeof(bool)*10001);

    int m,n;
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d",&m,&n);
        for(int j=m;j<=n;j++)
        {
            a[j]=false;
        }
    }
    int sum=0;
    for(int i=0;i<=L;i++)
    {
        if(a[i]==true)
            sum++;
    }
    printf("%d
",sum);
}

2：合并区间)：

思想是将所有区间存储在数组里面,对所有区间以下限为标准排序,然后从头至尾扫描区间数组,
合并区间的方法是：当前区间初始化为第一个区间,然后判断下一个区间的下限是否已经超过当前区间的上限,如果是这样的话,就无法继续合并了,那么就继续已经合并区间的长度,重新开始一次新的合并,否则的话,将下一个区间合并到当前区间起来。。。

#include<stdio.h>
#include<stdlib.h>
typedef struct Line{
    int start;
    int end;
}Line;

int compareLine(const void *a,const void *b)
{
    return ((Line *)a)->start-((Line *)b)->start;
}
int main()
{
    Line line[1001],tmp;
    int L,M;
    scanf("%d%d",&L,&M);
    
    for(int i=0;i<M;i++)
    {
        scanf("%d%d",&line[i].start,&line[i].end);
    }
    qsort(line,M,sizeof(Line),compareLine);

    int count=0;
    tmp=line[0];
    for(int i=1;i<M;i++)
    {
        if(line[i].start<=tmp.end)
        {
            tmp.end=line[i].end;
        }
        else
        {
            count=count+tmp.end-tmp.start+1;
            tmp=line[i];
        }
    }
    count=count+tmp.end-tmp.start+1;//为什么

    printf("%d
",L+1-count);
}

我们以(1,2) (2,4) (4,5) (6,7) (9,12)

开始tmp=line[0].

i=1 合并 tmp.end=4;

i=2 合并 tmp.end=5;

i=3; count=0+ (5-1)+1=5; tmp=line[3];

i=4; tmp.end<line[4].start; count=5+(7-6)+1=7; tmp=line[4];

退出

count=7+(12-9)+1=11;

参考：http://www.cppblog.com/csu-yx/archive/2011/11/07/159746.html

如果L很大，比如是40亿，无法开辟这么大的数组，怎么办？采用第二种方法可以。

编程之美也有类似的这个题目，其实，种树问题本质是区间重合判断。

一，问题：

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

2. 给定一个窗口区域和系统界面上的N个窗口，判断这个窗口区域是否被已有的窗口覆盖。

第一题源代码：

按照编程之美给出的提示。先用区间的左边界值对目标区间进行排序O(nlogn)，对排好序的区间进行合并O(n)，对每次待查找的源区间，用二分查出其左右两边界点分别处于合并后的哪个源区间中O(logn)，若属于同一个源区间则说明其在目标区间中，否则就说明不在。（为什么可以二分法）

#include<iostream>
#include<algorithm>
using namespace std;

#define MAX 10001
struct Line
{
    int low,high;
    bool operator<(const Line &L) const
    {
        return low<L.low;
    }
};
 

Line lines[MAX];   // 目标区间  
int ncount=0;//合并后区间个数

//用二分查找找出key所在的区间，以区间的low作为划分  
int getIndex(int key)
{
    int u,v;
    u=0;
    v=ncount-1;
    while(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;//目标区间个数
    cout<<"输入目标区间个数"<<endl;
    cin>>n;
    cout<<"输入目标区间"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>lines[i].low>>lines[i].high;
        cout<<endl;
    }
    cout<<"输入源区间个数"<<endl;
    int k;
    cin>>k;
    Line source[1001];
    for(int i=0;i<k;i++)
    {
        cin>>source[i].low>>source[i].high;
        cout<<endl;
    }
    //排序O(nlgn)
    sort(lines,lines+n);
    int tmp=lines[0].high;
    for(int i=1;i<n;i++)
    {
        if(tmp>=lines[i].low)
        {
            tmp=lines[i].high;
        }
        else
        {
            lines[ncount++].high=tmp;
            lines[ncount].low=lines[i].low;
            tmp=lines[i].high;
        }
    }
    lines[ncount++].high=tmp;
    
    for(int i=0;i<k;i++)
    {
        int s1=getIndex(source[i].low);
        int s2=getIndex( source[i].high);
        if(s1==s2 && source[i].high<=lines[s2].high)
        {
            cout<<"在区间内"<<endl;
        }
        else
        {
            cout<<"不再区间内"<<endl;
        }
    }
 

}

上面的程序有点错误：

在if (lasthigh >= lines[i].low)
lasthigh = lines[i].high;
不能直接修改lasthigh值，要判断if(lasthigh<lines[i].high)才能修改如{1,5}{2,4}则会合并成{1,4}.

转自：http://blog.csdn.net/tianshuai1111/article/details/7828961

下面的程序好点:

#include <iostream>
#include <algorithm>
using namespace std;

struct Line{
    int low,high;
    Line(int l=0,int h=0):low(l),high(h){}
    bool operator<(Line & other)
    {
        return low<other.low;
    }
};

const int MAX = 100;
Line lines[MAX];

//注意咱们搜索的数为刚好小于key的那个值
int BinarySearchLower(Line arr[],int len,int target)
{
    int low = 0;
    int high = len-1;

    while(low < high){
        int mid = (low + high)/2;
        if(arr[mid].low>=target)high = mid-1;
        else low = mid + 1;
            
    }
    return high;
}


int main()
{
    int n, k, i, j;  
    
    cin>>n;  // n是目标区间的个数,k是待查询的源区间的个数  
    for (i=0; i<n; i++)  
        cin >> lines[i].low >> lines[i].high;  

    sort(lines, lines+n);  
 
    int cnt = 0; //合并以后的区间数
    int lasthigh = lines[0].high;  

        //合并区间
    for(i=1; i<n; i++){
        if(lasthigh>=lines[i].low && lasthigh<lines[i].high)
            lasthigh = lines[i].high;
        else{
            lines[cnt].high = lasthigh;
            lines[++cnt].low = lines[i].low;
            lasthigh = lines[i].high;
        }

    }
    lines[cnt++].high = lasthigh;

    Line search = Line(1,6);

    int sLow = BinarySearchLower(lines,cnt,search.low);
    int sHigh = BinarySearchLower(lines,cnt,search.high);
    if(sLow==sHigh && search.high<=lines[sLow].high)//注意要判断
        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    system("pause");
    return 0;
}

我们输入三段目的区间：

1 4

2 3

7 8

要查找的是1-5,

经过合并后lines变成了:

1 4

2 3

注意2,3并没有去掉，在查找的时候有用。

上面的程序有问题。

解法：使用并查集

对每个区间合并到一个子树上，最后判断源区间的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");
}

画图理解：