56. Merge Intervals
1.問題
給予一個區間組成的集合, merge所有重疊的區間

2.想法
提問: interval間是否已排序?
parameter
Interval list
test input
說明想法
必須先排序Interval: overwrite sort operation
//define sort operation struct IntervalKey { inline bool operator() (const Interval &pLHS, const Interval &pRHS) { return pLHS.start < pRHS.start; } }; //sort vector sort(intervals.begin(), intervals.end(), IntervalKey());
比較Interval[i]與interval[cnt]:
如果有重疊, 則讓interval[cnt].end = interval[i].end
不然則將cnt++, 讓interval[i]加入新的interval[cnt]
測試計算複雜度
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) {}
* };
*/
class Solution {
public:
struct intervalKey {
inline bool operator()(const Interval& in1, const Interval& in2) {
return in1.start < in2.start;
}
};
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> res;
if (intervals.size() == 0) {
return res;
}
sort(intervals.begin(), intervals.end(), intervalKey());
int cnt = 0, n = intervals.size();
res.push_back(intervals[0]);
for (int i = 1; i < n; i++) {
if (intervals[i].start <= res[cnt].end) {
res[cnt].end = max(intervals[i].end, res[cnt].end);
} else {
cnt++;
res.push_back(intervals[i]);
}
}
return res;
}
};
4.Performance

Last updated