57. Insert Interval

發表於 | 分類於

problem

solution

類似56. Merge Intervals，先將newInterval 加進 intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ret;
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
            if(a[0] == b[0] ) return a[1]>b[1];
            return a[0]<b[0];
        });
        int n = intervals.size();
        int start = intervals[0][0], end = intervals[0][1];
        ret.push_back({start, end});
        for(int i=1;i<n;++i){
            vector<int>& cur = intervals[i];
            // overlap
            if(end >= cur[0]){
                end = max(end, cur[1]);
                ret.back()[1] = end;
            }
            else{
                ret.push_back(cur);
                start = cur[0];
                end = cur[1];
            }
        }
        return ret;
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(1)