github倉庫：https://github.com/lzed/leetcode
給一些互不重合并且已經(jīng)排好序的區(qū)間，現(xiàn)在加入一個(gè)新的區(qū)間b，要求將b合并進(jìn)去。
其實(shí)和區(qū)間合并那道題差不多，但是需要判斷的是我們的新區(qū)間b需要加入的位置。
當(dāng)新區(qū)間b.start <= a[i].start的時(shí)候，需要將b加入進(jìn)去。
有一些細(xì)節(jié)需要注意一下。但是感覺稍微有點(diǎn)難寫吶= =
首先，判斷第一個(gè)插入的是a[0]還是b：如果是a[0]，之后的循環(huán)就從1開始；否則從0開始。
對于之后的循環(huán)：
如果b.start <= a[i].start并且b還沒有被插入：我們插入b。否則，插入a。對于我們新加入的區(qū)間b，和原來集合里面的每一個(gè)區(qū)間i，只有這三種情況：
于是，我們分別分析一下這3種情況：
b.start > a.end：我們只需要加入a，然后i++。退出循環(huán)的條件：a全部加入。b.end < a.start：之后的a由題目知道是不重合的，并且從這個(gè)位置開始已經(jīng)不重合了，那么我們直接結(jié)束循環(huán)。a, b覆蓋：我們將a和b合成一個(gè)新的區(qū)間b，然后繼續(xù)循環(huán)。從上面可以知道，我們結(jié)束循環(huán)的條件為：1或者2。
從1退出的話，說明a全部加入，我們只需要加入b。從2退出的話，說明b及之后的a都應(yīng)加入。
并且，因?yàn)橹荒軓?或者2退出循環(huán)，說明我們的區(qū)間不存在覆蓋問題，因此在加入b和之后的a的過程中，只需要做的是push_back，而不需要進(jìn)行合并。
algorithm 1
class Solution {public: vector<Interval> insert(vector<Interval>& a, Interval b) { vector<Interval> ans; int n = a.size(); if (n) { int i = 1; bool flag = false; if (b.start <= a[0].start) { ans.push_back(b); i = 0; flag = true; } else { ans.push_back(a[0]); } for (; i < n; i++) { if (!flag && b.start <= a[i].start) { if (b.start <= ans.back().end) ans.back().end = max(ans.back().end, b.end); else ans.push_back(b); flag = true; i--; } else { if (a[i].start <= ans.back().end) ans.back().end = max(ans.back().end, a[i].end); else ans.push_back(a[i]); } } if (!flag) { if (b.start <= ans.back().end) ans.back().end = max(ans.back().end, b.end); else ans.push_back(b); } } else { ans.push_back(b); } return ans; }};algorithm 2
class Solution {public: vector<Interval> insert(vector<Interval>& a, Interval b) { vector<Interval> ans; auto it = a.begin(); for (it; it != a.end(); it++) { if (b.start > (*it).end) ans.push_back(*it); else if (b.end < (*it).start) break; else { b.start = min(b.start, (*it).start); b.end = max(b.end, (*it).end); } } //add b ans.push_back(b); //add remaining a for (it; it != a.end(); it++) ans.push_back(*it); return ans; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
