github倉庫：https://github.com/lzed/leetcode
給定若干個區間，合并這些區間。
先將區間排序，然后每次選定一個區間i，遍歷之后的區間j，找到最后一個能夠合并的區間后，合并。然后區間的起點的i跳轉到j + 1。
假如我們現在結果ans里面已經有一些區間了，最后一個區間為x（x.end一定是ans里面最大的）。
對于下一個區間y，如果y.start <= x.end，說明能夠和x重合，我們將x.end更新為max(x.end, y.end)。
如果不滿足能夠重合，說明是一個新的區間，然后放到結果里面去就好。
algorithm 1
bool cmp(Interval& a, Interval& b) { return a.start == b.start ? a.end < b.end : a.start < b.start;}class Solution {public: vector<Interval> merge(vector<Interval>& a) { sort(a.begin(), a.end(), cmp); vector<Interval> ans; int n = a.size(); for (int i = 0; i < n;) { int ed = a[i].end, j = i + 1; for (; j < n; j++) { if (a[j].start <= ed) ed = max(ed, a[j].end); else {j--; break;} } ans.push_back(Interval(a[i].start, ed)); i = j + 1; } return ans; }};algorithm 2
bool cmp(Interval& a, Interval& b) { return a.start == b.start ? a.end < b.end : a.start < b.start;}class Solution {public: vector<Interval> merge(vector<Interval>& a) { sort(a.begin(), a.end(), cmp); vector<Interval> ans; int n = a.size(); if (n) { ans.push_back(a[0]); for (int i = 1; i < n; i++) { if (a[i].start <= ans.back().end) ans.back().end = max(ans.back().end, a[i].end); else ans.push_back(a[i]); } } return ans; }};新聞熱點
疑難解答
