精华内容
下载资源
问答
  • 合并区间

    2019-08-06 18:38:48
    合并区间 题目: 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1...

    合并区间

    题目:

    给出一个区间的集合,请合并所有重叠的区间。

    示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
    示例 2:

    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

    代码如下:
    class Solution {
    public:
    	//比较器,排序规则
        static bool cmp(const vector<int>&a,const vector<int>&b )
        {
            if(a[0]==b[0])
                return a[1]>b[1];
            return a[0]<b[0];
        }
        vector<vector<int>> merge(vector<vector<int>>& intervals) {
            if(intervals.empty()) return intervals;
            vector<vector<int>> res;
            int count=0;//表示最终结果的第几个区间,刚开始为0
            sort(intervals.begin(),intervals.end(),cmp);
            vector<int> temp;
            temp.push_back(intervals[0][0]);
            temp.push_back(intervals[0][1]);
            res.push_back(temp);//将排序后的第一个区间放入
            for(int i=1;i<intervals.size();i++)
            {
                if(res[count][1]>=intervals[i][0])//若end>=start,可以合并
                {
                    if(res[count][1]<=intervals[i][1])判断前后哪个区间的end值较大,替换结果区间
                    {
                        res[count][1]=intervals[i][1];
                    }
                }
                else//不可以合并,此时必须往结果数组里放入这一区间
                {
                    count++;
                    temp[0]=intervals[i][0];
                    temp[1]=intervals[i][1];
                    res.push_back(temp);
                }
            }
            return res;
        }
    };
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 96,821
精华内容 38,728
关键字:

怎样合并区间