Given a collection of intervals, merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
這道題的題意是將重疊的區間合并起來。 首先需要將Intervals集合進行排序，按照第一個元素的升序進行排序。初始化結果集合只有第一個區間，將結果結合的最后一個元素和排序后的集合的當前下標的區間進行比較。eg. ,[a, b]和[c, d]當b <= c < d時，需要將這兩個區間合并為[a, d] 并存入結果中作為當前結果結合的最后一個元素。否則將[c, d] 存入結果集合中。如此循環直到集合訪問完畢，最后的結果也就得到了。
std::sort函數是全局的，如果第三個參數cmp不是靜態成員函數或者全局函數，運行都會報錯。非靜態函數是依賴于具體對象的，因此調用sort函數時，只能調用不依賴于對象的靜態函數cmp。
個人github代碼鏈接
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */class Solution {public: static bool cmp(Interval i, Interval j){ return i.start < j.start; } vector<Interval> merge(vector<Interval>& intervals) { if(intervals.size() == 0 || intervals.size() == 1) return intervals; vector<Interval> ans; sort(intervals.begin(), intervals.end(), cmp); ans.push_back(intervals[0]); for(int i = 1; i < intervals.size(); i++){ Interval tmp = ans[ans.size() - 1]; while(tmp.end >= intervals[i].end && i < intervals.size()) i++; if(i == intervals.size()) //confirm the border break; if(tmp.end >= intervals[i].start && tmp.end < intervals[i].end) { Interval t = Interval(tmp.start, intervals[i].end); ans.pop_back(); ans.push_back(t); } else if(tmp.end < intervals[i].start) { ans.push_back(intervals[i]); } } return ans; }};新聞熱點
疑難解答
