首页 > itarticle > 【leetcode】insert interval

【leetcode】insert interval

admin 11月 13, 2020 0

地址

https://leetcode.com/problems/insert-interval/description/

题目

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

思路

模拟下就好了，没什么好说的

代码


 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class  {
public:
    vector<Interval> insert(vector<Interval>& va, Interval vb) {
        vector<Interval> ans;
        Interval tmp;
        int n=va.size();
        if(n==0)
        {
            ans.push_back(vb);
            return ans;
        }
        if(vb.start > va[n-1].end)
        {
            for(int i=0; i<n; i++) ans.push_back(va[i]);
            ans.push_back(vb);
            return ans;
        }
        if(vb.end < va[0].start)
        {
            ans.push_back(vb);
            for(int i=0; i<n; i++) ans.push_back(va[i]);
            return ans;
        }
        for(int i=0,l,r; i<n; i++)
        {
            if(vb.start<=va[i].end)
            {
                if(vb.end<va[i].start)
                {
                    ans.push_back(vb);
                    while(i<n) ans.push_back(va[i++]);
                }
                else
                {
                    l=min(vb.start, va[i].start);
                    r=max(vb.end, va[i].end);
                    for(int j=i,ff=1; j<=n; j++)
                    if(j==n)
                    {
                        if(!ff) break;
                        tmp.start = l;
                        tmp.end = r;
                        ans.push_back(tmp);
                    }
                    else if(vb.end>=va[j].start)
                        r=max(r, va[j].end);
                    else
                    {
                        if(ff)
                        {
                            tmp.start = l;
                            tmp.end = r;
                            ans.push_back(tmp);
                            ff = 0;
                        }
                        ans.push_back(va[j]);
                    }
                }
                return ans;
            }
            ans.push_back(va[i]);
        }
        
        
    }
};