网站建设流程表,网站统计有哪些,扬州建设会计学会网站,公众号流量投放题目
以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间#xff0c;并返回 一个不重叠的区间数组#xff0c;该数组需恰好覆盖输入中的所有区间 。 示例 1#xff1a;
输入#xff1a;intervals …题目
以数组 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] 可被视为重叠区间。
C代码
#include iostream
#include vector
#include algorithm
using namespace std;/*
* 合并区间问题
* 排序定义区间的左右两边数字
* 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后
那么它们不会重合我们可以直接将这个区间加入数组 merged 的末尾
* 否则它们重合我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点
*/
vectorvectorint merge(vectorvectorint intervals) {if (intervals.size() 0) {return {};}sort(intervals.begin(), intervals.end());vectorvectorint merged;for (int i 0; i intervals.size(); i) {int L intervals[i][0], R intervals[i][1];if (!merged.size() || merged.back()[1] L) {merged.push_back({ L, R });}else {merged.back()[1] max(merged.back()[1], R);}}return merged;
}int main() {vectorvectorint intervals { {1,3},{2,6},{8,10},{15,18} };vectorvectorint merged merge(intervals);for (int i 0; i merged.size(); i) {for (int j 0; j merged[0].size(); j) {cout merged[i][j] ;}cout endl;}return 0;
}
分析
合并区间问题排序定义区间的左右两边数字。如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后那么它们不会重合我们可以直接将这个区间加入数组 merged 的末尾否则它们重合我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点。
