56. Merge Intervals 57. Insert Interval *HARD*-白红宇

56. Merge Intervals 57. Insert Interval *HARD*

阅读量：4556 次

发布时间：2019-06-08

本文共 3672 字，大约阅读时间需要 12 分钟。

1. Merge

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

/** * 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 Solution {public:    static bool compare(Interval a, Interval b)    {        if(a.start != b.start)            return a.start < b.start;        return a.end < b.end;    }    vector
     
       merge(vector
      
       & intervals) {        sort(intervals.begin(), intervals.end(), compare);        vector
       
         v;        int n = intervals.size(), i;        if(n<1)            return v;        for(i = 0; i < n; i++)        {            if(v.size() && intervals[i].start <= v[v.size()-1].end)                v[v.size()-1].end = max(intervals[i].end, v[v.size()-1].end);            else                v.push_back(intervals[i]);        }        return v;    }};

2. Insert

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

(1) 用上面的merge方法

/** * 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 Solution {public:    static bool compare(Interval a, Interval b)    {        if(a.start != b.start)            return a.start < b.start;        return a.end < b.end;    }    vector
     
       merge(vector
      
       & intervals) {        sort(intervals.begin(), intervals.end(), compare);        vector
       
         v;        int n = intervals.size(), i;        if(n<1)            return v;        for(i = 0; i < n; i++)        {            if(v.size() && intervals[i].start <= v[v.size()-1].end)                v[v.size()-1].end = max(intervals[i].end, v[v.size()-1].end);            else                v.push_back(intervals[i]);        }        return v;    }    vector
        
          insert(vector
         
          & intervals, Interval newInterval) {        intervals.push_back(newInterval);        return merge(intervals);    }};

(2)

/** * 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 Solution {public:    vector
     
       insert(vector
      
       & intervals, Interval newInterval) {        int n = intervals.size(), l, i;        vector
       
         v;        for(i = 0; i < n; i++)        {            if(newInterval.start > intervals[i].end)                v.push_back(intervals[i]);            else                break;        }        if(i >= n)        {            v.push_back(newInterval);            return v;        }        l = v.size();        v.push_back(intervals[i]);        if(newInterval.start < v[l].start)            v[l].start = newInterval.start;        while(i < n && newInterval.end > intervals[i].end)            i++;        if(i
        
         = intervals[i].start)            v[l].end = intervals[i++].end;        else            v[l].end = newInterval.end;        while(i