Cinte's Leetcode Record
0%

57. Insert Interval

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

57. Insert Interval

My vegetable exploded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int l = newInterval[0], r = newInterval[1];
        vector<vector<int>> ret;
        int i = 0;
        while(i < intervals.size() && intervals[i][1] < newInterval[0]) // 添加所有没有交叠的
            ret.push_back(intervals[i++]);
        while(i < intervals.size() && intervals[i][0] <= r) // 合并所有交叠的
        {
            l = min(l, intervals[i][0]);
            r = max(r, intervals[i][1]);
            ++i;
        }
        ret.push_back({l, r});
        while(i < intervals.size()) // 添加剩下的
            ret.push_back(intervals[i++]);
        return ret;
    }
};

三步走，先处理交叠前的，在处理正在交叠的，再添加剩下的

review

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ret;
        int i = 0, sz = intervals.size();
        for(; i < sz && intervals[i][1] < newInterval[0]; ++i)
            ret.push_back(intervals[i]);
        int l = newInterval[0], r = newInterval[1];
        for(; i < sz && r >= intervals[i][0]; ++i)
        {
            l = min(intervals[i][0], l);
            r = max(intervals[i][1], r);
        }
        ret.push_back({l, r});
        for(; i < sz; ++i)
            ret.push_back(intervals[i]);
        return ret;
    }
};