首页 > 代码库 > [Leetcode] merge intervals 合并区间

[Leetcode] merge intervals 合并区间

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

题意:给定一系列区间,合并重叠区间

思路:其实,个人觉得,题目的例子有一定误导性,以为区间已经按每个区间的start值排好序了。结果,毫无疑问,悲剧了。若是已经排好序,则,只需将当前区间的end值和下一个的start值比较,若是,before.end>=next.start,说明两个区间有重合,只需将后者的end值赋给前者的end值就行; before.end<next.start说明没有重叠,这样,就将前者存入结果,然后访问下一个就行。那么关键点来了,如何给这些区间排序?我们可以使用向算法传递函数,使用sort的第二版本,它接受第三个参数(为一个谓词),关于泛型算法,我将后续中给出较为详细的讲解。代码如下:

 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     static bool compare(const Interval &a,const Interval &b)
13     {
14         return a.start<b.start;
15     }
16 
17     vector<Interval> merge(vector<Interval> &intervals) 
18     {
19         
20         vector<Interval> res;
21         int len=intervals.size();  
22         if(len==0)  return res; 
23         sort(intervals.begin(),intervals.end(),compare);
24         res.push_back(intervals[0]);
25 
26         for(int i=1;i<len;++i)
27         {
28             int rLen=res.size();
29             if(res[rLen-1].end>=intervals[i].start)
30             {
31                 res[rLen-1].end=max(res[rLen-1].end,intervals[i].end);
32             }
33             else
34                 res.push_back(intervals[i]);
35         } 
36         return res;
37     }
38 };

在上述代码中,第28行,因为我们要实时访问res的最后一个区间的end值,但res是在变化的,所以通过这种方式访问,当然也可以通过使用back函数来访问以下方式:

 1 for(int i=1;i<intervals.size();++i)
 2 {
 3     if(res.back().end>=intervals[i].start)
 4     {
 5         res.back().end=max(res.back().end,intervals[i].end);
 6     }
 7     else
 8     {
 9         res.push_back(intervals[i]);
10     }
11 }

 

[Leetcode] merge intervals 合并区间