Leetcode 57 - Insert Interval

題目

Problem#

給你一堆不重疊的區間 intervals[i] = (s_i, e_i)，今天有個新的區間 newInterval，如果有重疊，則只留下最大區間，問你最後的區間 array 長怎樣

• 輸入
  • $N \le 10^4$ (intervals.size())
  • $0 \le s_i \le e_i \le 10^5$

想法#

重疊要怎麼判斷: 兩種情況疊左邊或是疊右邊 a[1] >= b[0] && b[1] >= a[0]。
先掃過一遍，重疊的話紀錄 index 以及最小左界 interval[0] 和最大右界 interval[1] 和代表重疊後剩下的區間 $k$
接著再掃一遍 interval ($i = [1, n)$) ，如果有重疊則把區間 $k$ 加到解中(一個就好)，如果沒有則直接把區間 $i$ 加到解中。
注意邊界條件: 如果重疊的區間，記得把 newInterval 也加到解中，懶得寫插入可以直接 sort 一下

• 時間複雜度: $\mathcal{O}(n)$ 如果掃一次插入，懶人 sort $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

2024/03/18: 2nd try 用 bitset

心得#

原本卡在最後蒐集解區間，後來發現直接紀錄有重疊的 index i.e. overlap[i] 代表第 i 個區間是跟別人重疊的，用於後面判斷。