題目連結:
題目意譯:
給定一陣列 intervals,其中 intervals[i] = [li, ri] 代表著區間 [li, ri),請移除掉所有被列表中另一個區間所覆蓋住的區間。
區間 [a, b) 被區間 [c, d) 所覆蓋住若且唯若 c ≦ a 且 b ≦ d。
回傳剩餘區間之數量。
限制:
1 ≦ intervals.length ≦ 1000
intervals[i].length == 2
0 ≦ li < ri ≦ 10 ^ 5
所有給定的區間皆相異。
範例測資:
範例 1:
輸入: intervals = [[1,4],[3,6],[2,8]]
輸出: 2
解釋: 區間 [3,6] 被 [2, 8] 所覆蓋,因此將其移除。
範例 2:
輸入: intervals = [[1,4],[2,3]]
輸出: 1
解題思維:
跟
這題其實很像。只是在本題中,排序的依據要改為先按照左端點「由小到大」排,左端點一樣再按右端點「由大到小」排。
這樣一來,基準線(沿用鏈結那一題的用詞)一開始即為排序後的第一個區間(也就是左端點最小中的那些區間之中右端點最右側的那一個區間)。因此位於基準線右端點以內的區間將會排在其後。
當我們掃過排序後的 intervals 時,如果有區間的右端點位於基準線的右端點之前,則表示該區間會被前面較大的區間所覆蓋住;反之,則不會被覆蓋住,因此此時需要更新基準線的右端點之值。
最後統計一下上述過程中有多少區間沒有被覆蓋住(包含第一個區間本身)即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。