类型: 数组
解题工具: C++ 语言
地址: https://leetcode-cn.com/problems/merge-intervals/
执行用时 : 36 ms, 在 Merge Intervals 的 C++ 提交中击败了 38.34% 的用户
内存消耗 : 12.4 MB, 在 Merge Intervals 的 C++ 提交中击败了 5.08% 的用户
- /*
- ** 给出一个区间的集合, 请合并所有重叠的区间.
- ** 示例 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:
- vector<vector<int>> merge(vector<vector<int>>& intervals) {
- int len = intervals.size();
- sort(intervals.begin(), intervals.end()); // 对起始区间进行排序
- vector<vector<int>> res;
- for (int i = 0; i <len;){
- int pointer = i;
- int maxn = intervals[i][1]; // maxn 定义为当前合并区间的最大值
- while(pointer+1 < len){
- if(intervals[pointer][1]>= intervals[pointer+1][0]) // 区间重合
- pointer++;
- else{ // 区间不重合, 向前查找, 直到找到一个大于 intervals[pointer+1][0] 的值
- int cur = pointer;
- while(cur>=0 && intervals[cur][1] <intervals[pointer+1][0]) cur--;
- if(cur>=0) pointer++; // 找到了, pointer++
- else break; // 找不到, 跳出
- }
- maxn = max(maxn,intervals[pointer][1]);
- }
- res.push_back({intervals[i][0],maxn});
- i = pointer + 1;
- }
- return res;
- }
- };
合并区间
来源: http://www.bubuko.com/infodetail-3045599.html