Insert Interval

今天药忘吃喽~ 2021-10-24 06:22 228阅读 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:  
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]`.

Runtime: 588ms

1 /**
     2  * Definition for an interval.
     3  * struct Interval {
     4  *     int start;
     5  *     int end;
     6  *     Interval() : start(0), end(0) {}
     7  *     Interval(int s, int e) : start(s), end(e) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
    13         vector<Interval> result;
    14         
    15         if(intervals.empty()){
    16             result.push_back(newInterval);
    17             return result;
    18         }
    19         
    20         int i = 0;
    21         int n = intervals.size();
    22         for(; i < n; i++){
    23             if(newInterval.end < intervals[i].start){
    24                 //result.push_back(newInterval);
    25                 break;
    26             }
    27             else if(newInterval.start > intervals[i].end){
    28                 result.push_back(intervals[i]);
    29                 continue;
    30             }
    31             else{
    32                 newInterval.start = min(newInterval.start, intervals[i].start);
    33                 newInterval.end = max(newInterval.end, intervals[i].end);
    34             }
    35         }
    36         
    37         result.push_back(newInterval);
    38             
    39         for(; i < intervals.size(); i++)
    40             result.push_back(intervals[i]);
    41         
    42         return result;
    43     }
    44 };

转载于:https://www.cnblogs.com/amazingzoe/p/4851866.html