Code & Func

第24天

emmm，又是一道10分钟刷完的题目——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].

这个题目要考虑的就是怎么才能避免不断的插入删除。

其实再后来尝试优化的时候，就是陷入这个误区，尝试的写一个O(n)的算法出来，但是发现要不断的遍历和插入和删除元素，我们知道这对vector来说时比较耗时的。

我们先确定什么时候两个Intervals需要merge,考虑i1,i2,只有i1.end > i2.start，这时i1和i2就应该merge成{i1.start,i2.end}

先对intervals按start排序
将第一个元素放入ret，因为这时start是最小的，我们现在只需要寻找end即可
我们考察第二个元素，如果第二个元素的start小于第一个元素的end，我们就将修改end,并考察第三个元素，如果不成立，说明当前元素的end就已经找到了（因为start < end）

1
vector<Interval> merge1(vector<Interval>& intervals) {
2
    if (intervals.size() <= 1) return intervals;
3

4
    sort(intervals.begin(),intervals.end(),[](const Interval &a,const Interval b) -> bool{
5
        return a.start < b.start;
6
    });
7

8
    vector<Interval> ret;
9
    ret.push_back(intervals[0]);
10
    int last = 0;
11

12
    for(int i = 1;i < intervals.size();i++) {
13
        if (ret[last].end >= intervals[i].start)
14
            ret[last].end = max(intervals[i].end,ret[last].end);
15
        else {
7 collapsed lines
16
            ret.push_back(intervals[i]);
17
            last++;
18
        }
19
    }
20

21
    return ret;
22
}

还有在dicuss中看到的答案，但是这个需要做两次sort，所以效率不会比上面的方法高:

1
public List<Interval> merge(List<Interval> intervals) {
2
    // sort start&end
3
    int n = intervals.size();
4
    int[] starts = new int[n];
5
    int[] ends = new int[n];
6
    for (int i = 0; i < n; i++) {
7
        starts[i] = intervals.get(i).start;
8
        ends[i] = intervals.get(i).end;
9
    }
10
    Arrays.sort(starts);
11
    Arrays.sort(ends);
12
    // loop through
13
    List<Interval> res = new ArrayList<Interval>();
14
    for (int i = 0, j = 0; i < n; i++) { // j is start of interval.
15
        if (i == n - 1 || starts[i + 1] > ends[i]) {
6 collapsed lines
16
            res.add(new Interval(starts[j], ends[i]));
17
            j = i + 1;
18
        }
19
    }
20
    return res;
21
}