首页 > 代码库 > Leetcode--Merge Intervals

Leetcode--Merge Intervals

Problem Description:

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

分析:按照要求将区间合并,首先将按照按起点排序,然后从前往后依次合并即可,首先判断相邻两个区间是否有交集,没有则直接将前一个保存,有交集的两个区间合并之后不能直接保存,需要和下一个区间比较是否有交集,没有交集才能保存,代码中利用一个temp区间保存当前合并后的区间,直到最后合并完成。具体代码如下:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */


 struct cmpLess
{
         bool operator ()(const Interval & a,const Interval & b)
         {
              return a.start<b.start;
         }
};

 
class Solution {
public:


    Interval merge(Interval a,Interval b)
    {
        Interval c;
        c.start=min(a.start,b.start);
        c.end=max(a.end,b.end);
        return c;
    }

    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> res;
        if(intervals.size()==0)
            return res;
        Interval temp;
        int flag=0;//判断上一次是否有区间合并
        sort(intervals.begin(),intervals.end(),cmpLess());
        
        for(int i=1;i<intervals.size();i++)
        {
            if(flag==0)
            {
                if(intervals[i-1].end<intervals[i].start)
                    res.push_back(intervals[i-1]);
                else
                {
                    temp=merge(intervals[i-1],intervals[i]);
                    flag=1;
                }
                
            }
            else
            {
                if(temp.end<intervals[i].start)
                {
                    res.push_back(temp);
                    flag=0;
                }
                else
                    temp=merge(temp,intervals[i]);
            }
        }
        if(flag==0)
            res.push_back(intervals[intervals.size()-1]);
        else
            res.push_back(temp);
        return res;
    }
};