核心思想，额外空间，分三段处理，时间复杂度O(N)
/* * @lc app=leetcode id=57 lang=cpp * * [57] Insert Interval */ // @lc code=start class Solution { public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { vector<vector<int>> ans; int N = intervals.size(); int loc = 0; while(loc < N && newInterval[0] > intervals[loc][1]){ ans.push_back(intervals[loc++]); } while(loc < N && newInterval[1] >= intervals[loc][0]){ newInterval[0] = min(newInterval[0], intervals[loc][0]); newInterval[1] = max(newInterval[1], intervals[loc++][1]); } ans.push_back(newInterval); while(loc < N){ ans.push_back(intervals[loc++]); } return ans; } }; // @lc code=end