【Leetcode】57. Insert Interval（模拟）

野性酷女 2022-02-28 03:54 160阅读 0赞

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].

题目大意：

给出一个不重叠的序列，插入一个新区间，输出区间重叠之后的结果。

解题思路：

本题与56题极为相似，只需在开始时将新区间push\_back到intervals中，然后按照56题中方法计算即可。

56题解题连接：[https://blog.csdn.net/qq\_29600137/article/details/88766866][https_blog.csdn.net_qq_29600137_article_details_88766866]

class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
    		
    		intervals.push_back(newInterval);
    		
    		sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){
    			return a.start < b.start;
    		});
    		
            for(int i = 0; i<intervals.size(); i++){
                printf("%d %d\n", intervals[i].start, intervals[i].end);
            }
            
    		Interval *cor = &intervals[0];
    		
    		int cor_loc = 0;
    		
    		for(int i = 1; i<intervals.size(); i++){
    			if (intervals[i].start <= cor->end){
    				cor->end = max(cor->end, intervals[i].end);
    			}
    			else{
    				intervals[cor_loc++] = *cor;
    				cor = &intervals[i];
    			}
    		}
    		
    		intervals[cor_loc++] = *cor;
    		intervals.resize(cor_loc);
    		
    		return intervals;
    		
        }
    };

[https_blog.csdn.net_qq_29600137_article_details_88766866]: https://blog.csdn.net/qq_29600137/article/details/88766866