ZJ b966; APCS2016第三題 線段覆蓋長度

明天要發學測成績單了(抖

希望一切順利。然後禮拜六要APCS，果然不少同學在寫考古題呢

今天就來寫其中一題的題解吧

題目有好人放在zero judge上了
連結：ZJ b966

題目：給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。
例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。

做法：

重疊的部分只能計算一次，而該怎麼有效率地判斷重疊呢?

這裡先將資料以左端點排序，讓每個線段的左端點在前一個線段的右方，並維護當前延伸最遠的右端座標R。

如此一來，就可以利用R與當前線段的端點座標來判斷重疊的部分。

到這可以先想想會有哪幾種狀況，然後大概就知道怎麼寫了。

這裡列出我在寫這題時歸納出來的狀況：

1. 當前線段之右端在R的左側，代表當前線段被包含於前一個線段之中。
2. 當前線段之左端在R的右側，代表當前線段與前一個線段沒有交集。
3. 當前線段之左端在R的左側(且右端在R的右側)，發現部分重疊，故減去重疊的長度。

另外，在排序時，若左端點一樣，可以將右端點大而小排序，顯然地，在掃過去計算的時候，同一個左端點的線段只要算第一個就好了。

code:

if裡寫的比較精簡，重疊的長度乘上一個bool值為是否有重疊，True, False分別會乘上1, 0。