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

该题目用Greedy,先对start的时间进行从小到大sort,然后记录第一次的start和end时间。

之后对所有intervals进行循环遍历,这其中会有三种情况:

  1. intervals[i].start > end,说明下一段interval的起始时间已经超出当前记录的时间段,所以要将之前记录的时间段push进结果vector,并更新记录时间段start和end。
  2. intervals[i].start < end & intervals[i].end > end,说明下一段interval前部分和之前的记录段重合,后部分会超出原先的记录的end时间,于是直接更新end。
  3. intervals[i].end  < end,说明下一段interval被完全覆盖在原来记录的时间段内,所以不做任何操作。

这样到最后的结果vector中记录的即为所有interval的并集。

Solution:


/**
 * 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<Interval> merge(vector<Interval>& intervals) {
                if(intervals.size() == 0) return intervals;
                vector<Interval> res;
                int start, end;
                sort(intervals.begin(), intervals.end(), 
                        [](Interval a, Interval b){ return a.start < b.start; } ); //C++ 11 sort structure
                start = intervals[0].start;
                end = intervals[0].end;
        
                for(int i = 0; i < intervals.size(); ++i)
                {
                        if(intervals[i].start > intervals[i].end) continue;
                        if(intervals[i].start > end)
                        {
                                Interval interval(start, end);
                                res.push_back(interval);
                                start = intervals[i].start;
                                end = intervals[i].end;
                        }
                        else if(intervals[i].end > end) end = intervals[i].end;
            
                        if(i == intervals.size() - 1) 
                        {
                                Interval interval(start, end);
                                res.push_back(interval);
                        }
                }
        
                return res;
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *