1. 題目

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].

2. 思路

先排序，排序規(guī)則是start小的在前，如果start相等則end大的在前。
然后從前往后遍歷，如果當(dāng)前要處理的節(jié)點(diǎn)可以歸并到當(dāng)前已歸并的末節(jié)點(diǎn)上，則歸并上去。
最后將已歸并節(jié)點(diǎn)之后的空間清掉。

3. 代碼

/*** Definition for an interval.* struct Interval {* int start;* int end;* Interval() : start(0), end(0) {}* Interval(int s, int e) : start(s), end(e) {}* };*/bool cmp(Interval& i, Interval& j) {return i.start < j.start || i.start == j.start && i.end > j.end; }class Solution { public:// 先排序, 起點(diǎn)小終點(diǎn)大在前。// 然后從前往后遍歷, 將可以歸并的點(diǎn)進(jìn)行歸并填入，最后多出來的元素刪掉vector<Interval> merge(vector<Interval>& intervals) {if (intervals.size() == 0) { return intervals; }sort(intervals.begin(), intervals.end(), cmp);int fill = 0;int merge = 1;while (merge < intervals.size()) {Interval& fi = intervals[fill];Interval& mi = intervals[merge];if (fi.end >= mi.start) {if (mi.end > fi.end) {fi.end = mi.end;}} else {fill++;if (fill != merge) {intervals[fill] = intervals[merge];}}merge++;}intervals.resize(fill+1);return intervals;} };

總結(jié)

以上是生活随笔為你收集整理的【leetcode】56. Merge Intervals 相邻线段归并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。