Re: [問題] 檢查數字範圍是否相互重疊

[bleed1979 (十三)]

如果note數超過10000筆，我會建議開40萬的bool陣列。
空間多一點，但用O(1)在比較。

如果note數不多，

bool overlap(Object& A, Object& B)
{
  return((B.left >= A.left && B.left <= A.right) ||
        (B.right >= A.left && B.right <= A.right));
}

if(overlap(留下的, 要刪除的) || (overlap(要刪除的, 留下的))
  刪除 - 要刪除的；
else
  將"要刪除的"加入"留下的"陣列。

您還是必須花一個陣列(或vector)紀錄"留下的"的索引列。
然後每次都搜尋"留下的"那個陣列。


Bleed


※ 引述《herman602 (奸商)》之銘言：
:         ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
:              ( 未必需要依照此格式，文章條理清楚即可 )
: 遇到的問題： (題意請描述清楚)
: 我把一份文件讀進來
: 格式大概長這樣子
: Note 242655 246400  81
: Note 242795 243180  71
: Note 243180 246400  74
: Note 246400 246785  78
: Note 246400 248430  81
: 我要檢查每個Note的範圍
: 有沒有相互重疊
: 像以上有4個Note的範圍有相互重疊到
: 希望得到的正確結果：
: 只要偵測到有重疊, 直接移除該行
: 程式跑出來的錯誤結果：
: N/A
: 開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
: C++/CLI
: 有問題的code： (請善用置底文標色功能)
: 補充說明：
: 我實在想好久想不到一個適當的演算法

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.43.126.82
→ herman602:感謝你!!! 我也來試試看這個方法!!
推 chrisdar:return((A.left <= B.right) || (b.left <= A.right));
→ chrisdar:條件 X.left <= X.right
推 chrisdar:                           &&