57

57. Insert Interval (Hard)

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Related Topics:
Array, Sort

Similar Questions:

• Merge Intervals (Medium)
• Range Module (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/insert-interval/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int s = newInterval[0], e = newInterval[1];
        vector<vector<int>> ans;
        for (auto &intv : intervals) {
            if (s > e) ans.push_back(intv);
            else if (intv[0] > e) { 
                ans.push_back({ s, e });
                s = e + 1;
                ans.push_back(intv);
            } else if (intv[1] < s) ans.push_back(intv);
            else {
                s = min(s, intv[0]);
                e = max(e, intv[1]);
            }
        }
        if (s <= e) ans.push_back({ s, e });
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/insert-interval/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int s = newInterval[0], e = newInterval[1], pos = 0;
        vector<vector<int>> ans;
        for (auto &intv : intervals) {
            if (intv[1] < s) {
                ans.push_back(intv);
                ++pos;
            } else if (intv[0] > e) ans.push_back(intv);
            else {
                s = min(s, intv[0]);
                e = max(e, intv[1]);
            }
        }
        ans.insert(begin(ans) + pos, { s, e });
        return ans;
    }
};