最近剛好有寫到比對是否有區間重覆的程式,擔心自己寫的不夠完整找了一些人的寫法,最後在 Stack Overflow 上看到最清楚的解答,特此誌之供日後查閱。 以下的圖、演算法與版權皆屬於原作者。
區間重疊的可能性就只有上圖中 Case 1 ~ Case 4,其Case 5 若 B.End 與 A.Start相等時,亦不算重疊。
因此若寫成code時,只要一列 就能算出是否重疊。
bool overlap = a.Start < b.End && b.Start < a.End;
邏輯上解釋:A的起點必須在B的終點之前,否則就是不重疊;以另一端點來看,A的終點也必須在B的起點之前才有重疊。 因此可得知上列的驗證為重疊成立的充分條件。
留言