57 - Insert Interval

解法一 - 暴力法

``````class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
intervals.push_back(newInterval);

sort(intervals.begin(), intervals.end(), [](const vector<int>& i1, const vector<int>& i2) {
return i1[0] < i2[0];
});

vector<vector<int>> res = {intervals[0]};

for(int i = 1; i < intervals.size(); ++i) {
if(res.back()[1] < intervals[i][0]) {
res.push_back(intervals[i]);
}
else {
res.back()[1] = max(res.back()[1], intervals[i][1]);
}
}

return res;
}
};
``````

解法二 - 只 merge 需要 merge 的 interval

``````class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int i = 0;

// Skipping all intervals which ends before newInterval starts
vector<vector<int>> res;
while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
res.push_back(intervals[i]);
++i;
}

// Keep merging until intervals[i] starts after newInterval
while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
++i;
}
res.push_back(newInterval);

// Push all left inter
while(i < intervals.size()) {
res.push_back(intervals[i]);
++i;
}

return res;
}
};
``````

Runtime: 16 ms, faster than 82.65% of C++ online submissions for Insert Interval. Memory Usage: 12.2 MB, less than 100.00% of C++ online submissions for Insert Interval.