57. Insert Interval
1.問題
給予一個不重疊的intervals list並插入一個新的interval, 必要時必須融合intervals

2.想法
提問: interval間是否已排序?
function header, parameter
test input
說明想法 (同56.Merge Interval)
必須先排序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[i - 1]:
如果有重疊, 則讓interval[cnt].end = interval[i].end
不然則將interval[i]加入
測試計算複雜度
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& pLHS, const Interval& pRHS) {
return pLHS.start < pRHS.start;
}
};
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> res;
int size = intervals.size();
if (size == 0) {
res.push_back(newInterval);
return res;
}
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end(), IntervalKey());
int cnt = 0;
for (int i = 1; i < size + 1; i++) {
if (intervals[i].start <= intervals[cnt].end && intervals[i].end >= intervals[cnt].start) {
intervals[cnt].end = max(intervals[cnt].end, intervals[i].end);
} else {
++cnt;
intervals[cnt].start = intervals[i].start;
intervals[cnt].end = intervals[i].end;
}
}
res.assign(intervals.begin(), intervals.begin() + cnt + 1);
return res;
}
};
Last updated