跳到主要內容

區間是否有重疊的演算法 An algorithm to check whether intervals overlap.

 最近剛好有寫到比對是否有區間重覆的程式,擔心自己寫的不夠完整找了一些人的寫法,最後在 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的起點之前才有重疊。 因此可得知上列的驗證為重疊成立的充分條件。

留言

這個網誌中的熱門文章

自然人憑證讀卡機驅動程式

鳥毅用的是第一代的自然人憑證讀卡機,EZ100PU(後來有同事買EZmini可以讀SIM卡似乎更好),每年報稅時用一次。 本來只是要申請些政府業務,一時之間找不到光碟,沒想到在 驅動程式下載 居然看到Linux和Mac的驅動程式,剩下的就是政府單位的網頁和程式應該改版了吧!!!

DBeaver 介面語言

DBeaver是我個人頗常用的一套跨平台Database管理工具,最近升級後發現Windows版本居然變成簡體中文,而且無法切換為英文。

如何將較高版本SQL Server複製到低版本SQL Server (降級為舊版)並保留權限及資料庫圖表

一般若是要將SQL Server裡的Database轉往其他Server時,最簡單的方式就是備份(Backup)後再還原(Restore),或者是䣃離(detach)後附加(attach)。 但是很不幸地,若是由較低版本(e.g. 2008)到較高版本(e.g. 2012)要怎麼辦呢?