Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Merge Intervals

Leetcode algorithms 第 56 题: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].

解答

区间合并问题。先把所有的区间按起点坐标排序,然后逐个扫描所有的区间,记录当前的起点和终点:

  • 如果新的区间的起点在这里面,则可以合并成为一个新的区间,更新起点和终点。
  • 否则原有区间成为一个独立的区间,新的区间成为当前的区间。

具体代码如下:

/**
 * 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:
    struct cmp //区间排序仿函数
    {
        bool operator()(const Interval &a, const Interval &b)
        {
            return a.start < b.start || (a.start == b.start && a.end < b.end);
        }
    };

    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> ans;
        if (intervals.empty()) return ans;
        
        sort(intervals.begin(), intervals.end(), cmp()); //按起点排序
        int st = intervals[0].start, ed = intervals[0].end;
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i].start > ed) //新的区间
            {
                ans.push_back(Interval(st, ed));
                st = intervals[i].start, ed = intervals[i].end;
            }
            else if (intervals[i].end > ed) //可以合并
                ed = intervals[i].end;
        }
        ans.push_back(Interval(st, ed));
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论