天天看點

求解重疊區間

方法一:

對于給定的兩個區間(a,b)和(c,d),顯然,當且僅當a≤d&&c<=b時才會有重疊區間,

此時重疊區間長度L為        L=min(b,d)−max(a,c)    

方法二:

建立一個區間段數組,例如[a,b),将[a,a+1)...[b-1,b)的區間段加1,[c,d),将[c,c+1)...[b-1,b)的區間段加1,最後統計為2的區間數量即為重疊區間的長度