题解 | #合并区间#

NC37 合并区间

题意分析：

将所给的多个区间，将重叠的区间的进行合并。

题解一（贪心）：

如有区间如下：

[[10,30],[20,60],[80,100],[150,180]]

合并的结果为：

[[10,60],[80,100],[150,180]]

区间[10，30]和区间[20，60]有重叠的部分，合并后就成为了[10，60]。合并过程如下

将区间[10，30]的end和区间[20，60] 的start比较，30>20，说明有重叠，更新区间[10，30]的end 为区间[10，30]的end和区间[20，60]的end的较大值。
如果两个区间没有交集，如区间[10，60]和区间[80，100]，前一区间的end小于下一区间的start。直接将没有重合的区间加入到结果中。

代码实现如下：

static bool cmp(Interval &a, Interval &b) {
    return a.start < b.start;
}

vector<Interval> merge(vector<Interval> &intervals) {
    if(intervals.size()<2) return intervals;
    vector<Interval> ret;
    //按照区间的start从小到大排序
    sort(intervals.begin(), intervals.end(),cmp);
    //把第一个区间加入到结果中
    ret.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); i++) {
        //从第二个开始，拿该该区间的start与位于结果区间vector的最后一个区间的end比较
        if (intervals[i].start <= ret.back().end) {
            //如果有重叠，更新ret.back的end
            ret.back().end = max(ret.back().end, intervals[i].end);
        } else {
            //没有重叠，直接加入即可
            ret.push_back(intervals[i]);
        }
    }
    return ret;
}

时间复杂度： $O(nlg\ n)$ ，时间开销主要在对区间的排序上。

空间复杂度： $O(1)$ ，没有申请使用额外的空间。

题解二（动态规划）：

任何贪心本质上都可以改成动态规划。对于给定的一个区间，我们对他的操作只有两种，第一种直接加入到最后结果中，第二种是与结果中的一个区间进行合并。

假设现在有区间intervals[i]，结果区间为 $vector<Interval>ret$ ,我们设置一个index，表示现在ret中哪个位置需要合并，合并的条件为ret[index-1].end>=interval[i].start, 那么有如下转移方程：

ret[index-1].start = min(ret[index-1].start,intervals[i].start)

ret[index-1].end = min(ret[index-1].end,intervals[i].end)

发生了合并，index不发生改变

如果没有发生合并，那么直接添加该区间，index更新到新的位置

vector<Interval> merge(vector<Interval> &intervals) {

    sort(intervals.begin(), intervals.end(), cmp);
    if (intervals.size() <= 1) {
        return intervals;
    }
    vector<Interval> ret(intervals.size());
    ret[0].start = intervals[0].start;
    ret[0].end = intervals[0].end;
    int index = 1;
    for (int i = 0; i < intervals.size(); i++) {
        if (ret[index - 1].end >= intervals[i].start) {
            ret[index- 1].start= min(ret[index - 1].start, intervals[i].start);
            ret[index - 1].end = max(ret[index - 1].end, intervals[i].end);
        } else {
            index++;
            ret[index- 1].start = intervals[i].start;
            ret[index - 1].end = intervals[i].end;
        }
    }
    return vector<Interval>(ret.begin(),ret.begin()+index);
}

时间复杂度： $O(nlg \ n)$ ,我们对所有区间进行了一次排序

空间复杂度： $O(n)$ ，n为区间长度。