判斷兩個區間是否重疊_總結

（1）問題：

假設有兩個區間M(s1, e1)和N(s2, e2)，如何判斷兩個區間是否有交集？

（2）解答：

命題A: M和N相離，且M在前N在後。（當 s2 > e1時成立）

命題B: M和N相離，且M在後N在前。  ( 當 s1 > e2時成立)

如果命題(A or B)為真，則兩個區間每有交集。

則如果命題(A or B)都為假，則兩個區間有交集。

注:

其實重疊的有4種，兩種相交，兩種包含；

根據德摩根定律可知：

！(A or B) = !A and !B

也就是說 (s2 <= e1) and (s1 <= e2)

(3)代碼實作：

#include <iostream>

using namespace std;

typedef struct{

    int start;

    int end;

}Interval;

bool isOverlap_1(Interval interval1,Interval interval2){

    if(interval1.end<interval2.start || interval1.start>interval2.end)

        return false;

    return true;

}

bool isOverlap_2(Interval interval1,Interval interval2){

    if(max(interval1.start,interval2.start)<=min(interval1.end,interval2.end))

        return true;

    return false;

}

int main()

{

    Interval interval1,interval2;

    while(1){

        if(cin>>interval1.start && cin>>interval1.end && cin>>interval2.start && cin>>interval2.end){

            if(isOverlap_2(interval1,interval2))

                cout<<"Overlap"<<endl;

            else

                cout<<"Non-overlap"<<endl;

        }

    }

    return 0;

}