凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 56. Merge Intervals

分类:algorithm| 发布时间:2017-01-25 17:39:00


题目

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

题意

给出一组表示间距的数字,合并所有重叠的间距。

解法

/**
 * 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) {
        sort(intervals.begin(), intervals.end(), [](const Interval &l, const Interval &r) -> bool {return l.start < r.start;});

        vector<Interval> ret;
        ret.reserve(intervals.size());
        int j = 0;
        for (auto &i: intervals) {
            while (j < ret.size()) {
                Interval &tmp = ret[j];
                if (tmp.start <= i.start && tmp.end >= i.start) {
                    tmp.end = max(tmp.end, i.end);
                    break;
                }

                if (i.start <= tmp.start && i.end >= tmp.start) {
                    tmp.start = i.start;
                    tmp.end = max(tmp.end, i.end);
                    break;
                }

                ++j;
            }

            if (j == ret.size()) {
                ret.push_back(i);
            }
        }

        return ret;
    }
};