56. Merge Intervals

发表于 | 分类于

每日一题 2019 - 04 - 02

题目：

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

解答：

这个题让我们做数组里面的区间合并，思路大致如下：

  • 首先对整个 Intervals 进行排序，排序规则为 start 小的在前面，这样保证我们在后面运算时候一定可以维持数据的有序性

  • 其次创立临时变量数组，我们每次都拿着临时变量数组 temp 跟当前待加入的数组 intervals[i] 对比：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    if( intervals[i].start >= temp[temp.size()-1].start && intervals[i].end > temp[temp.size()-1].end)
    {
        temp[temp.size()-1].end = intervals[i].end ;
    }
    else if(intervals[i].start < temp[temp.size()-1].start && intervals[i].end > temp[temp.size()-1].end)
    {
        temp[temp.size()-1].start = intervals[i].start ;
        temp[temp.size()-1].end = intervals[i].end ;

    }

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool cmp(Interval a,Interval b)
{
    return a.start < b.start ;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<Interval> temp ;
        if(intervals.size() == 0)
        {
            return temp ;
        }
        int size = intervals.size();
        int before = intervals[0].start ;
        int end = intervals[0].end ;
        Interval now(before,end);
        temp.push_back(now);
        for(int i = 1 ; i < size  ; i ++ )
        {
            if( intervals[i].start > temp[temp.size()-1].end )
            {
                temp.push_back(intervals[i]);
            }
            else
            {
                 if( intervals[i].start >= temp[temp.size()-1].start && intervals[i].end > temp[temp.size()-1].end)
                 {
                     temp[temp.size()-1].end = intervals[i].end ;
                 }
                else if(intervals[i].start < temp[temp.size()-1].start && intervals[i].end > temp[temp.size()-1].end)
                {
                    temp[temp.size()-1].start = intervals[i].start ;
                    temp[temp.size()-1].end = intervals[i].end ;
                    
                }
            }
        }
        return temp ;
    }
};
0%
undefined