以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
我采用了纯暴力解法，仅作记录，参考价值不高。正确的解法应当是先按左边界进行排序后再直接合并区间。
/* * @lc app=leetcode.cn id=56 lang=cpp * * [56] 合并区间 */ #include<bits/stdc++.h> using namespace std; // @lc code=start class Solution { public: vector<vector<int>> result; int visit[10005]={0}; //0表示未被访问，-1表示左边界，1表示右边界，2表示内部，3表示一个数（左右边界相同) vector<vector<int>> merge(vector<vector<int>>& intervals) { for (int i=0;i<intervals.size();++i){ int start=intervals[i][0]; int end=intervals[i][1]; //对于点（左右边界相同），有两种情况：1.首次访问，更新为点；2.其他情况直接同化 if (start==end){ if (visit[start]==0) visit[start]=3; continue; } //对于左边界，存在三种情况：1.首次访问或为点，更新为左边界；2.为其他区间的右边界，更新为内部点；3.为其他区间的左边界或者内部，无需更新； if (visit[start]==0||visit[start]==3) visit[start]=-1; else if (visit[start]==1) visit[start]=2; //对于右边界，同理：1.首次访问或为点，更新为右边界；2.为其他区间的左边界，更新为内部点；3.为其他区间的右边界或者内部，无需更新； if (visit[end]==0||visit[end]==3) visit[end]=1; else if (visit[end]==-1) visit[end]=2; for (int j=start+1;j<end;++j){ visit[j]=2; } } vector<int> temp; for (int i=0;i<=10000;++i){ if (visit[i]==3){ result.push_back({i,i}); } if (visit[i]==-1){ temp.push_back(i); } if (visit[i]==1){ temp.push_back(i); result.push_back(temp); temp.clear(); } } return result; } }; // @lc code=end