Insert Interval

https://leetcode.com/problems/insert-interval/description/

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Thoughts

intervals分为三段, 第一段end都在newInterval前, 第二段interval.start 都在newInterval.end前, 和newInterval有overlapping, 把interval不断合并到newInterval中, 第三段是剩下的.

Code

/*
 * @lc app=leetcode id=57 lang=cpp
 *
 * [57] Insert Interval
 */
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int N = intervals.size(), i = 0;
        for (; i < N; ++i) {
            if (intervals[i][1] < newInterval[0]) res.push_back(intervals[i]);
            else break;
        }
        for (; i < N; ++i) {
            if (newInterval[1] < intervals[i][0]) break;
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
        }
        res.push_back(newInterval);
        for (; i < N; ++i) {
            res.push_back(intervals[i]);
        }
        return res;
    }
};

Analysis

时间复杂度O(N).