gogoWebsite

1. Question description

Give you a list of intervals without overlapping, sorted by the intervals starting endpoint, where intervals[i] = [starti, endi] represents the beginning and end of the i-th interval, and intervals are arranged in ascending order of starti. Also given an interval newInterval = [start, end] indicates the beginning and end of another interval.

Insert interval newInterval in intervals so that intervals are still arranged in ascending order in starti and do not overlap between intervals (if necessary, the intervals can be merged).

Returns the intervals after insertion.

Note that you do not need to modify intervals in place. You can create a new array and then return it.

2. Test cases

Example 1:

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

Example 2:

Enter: intervals= [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]Output:[[1,2],[3,10],[12,16]]Explanation: This is because of the new interval[4,8]and[3,5],[6,7],[8,10]overlapping.

hint:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105intervals by starti in ascending order
 newInterval.length == 2
0 <= start <= end <= 105

3. Problem-solving ideas

1. Basic ideas:
   Travel the interval sequence and judge the timing of merging and inserting.
   • Merge timing: Merge as long as there is overlap
   • Insert timing: First, insert the intervalstartiIt should be smaller than the interval traversedstarti;Secondly, the insertion interval has not been inserted yet.
2. Specific ideas:
   • Definition: ans is used to store the answer; is_insert is used to determine whether to insert, initialized to false;
   • Traversal interval sequence: determine whether the current interval and the insertion interval can be merged. If it can be merged, merged; if it cannot be, judge whether the insertion interval can be inserted, and if it can be inserted;
   • After traversing, you must finally determine whether the insertion interval is inserted. If there is no, it means that the starti of the insertion interval is the largest, and then it is inserted at the end of the interval sequence;
   • Return result ans .

4. Reference code

Time complexity:$\mathrm{O}(n)$
Space complexity:$\mathrm{O}(n)$【Space of answers】

class Solution {
public:
    bool is_overlap(vector<int>& x, vector<int>& y) {
        if (x[0] > y[1] || x[1] < y[0])
            return false;
        return true;
    }
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        bool is_insert = false;

        for (auto& interval : intervals) {
            if (is_overlap(interval, newInterval)) {
                newInterval[0] = min(interval[0], newInterval[0]);
                newInterval[1] = max(interval[1], newInterval[1]);
            } else {
                if (interval[0] > newInterval[0] && !is_insert) {
                    ans.push_back(newInterval);
                    is_insert = true;
                }
                ans.push_back(interval);
            }
        }
        if (!is_insert) {
            ans.push_back(newInterval);
        }

        return ans;
    }
};