作文记录：合并区间的技巧与应用

0、前言

本篇博客是一个题解&＃xff0c;具体题目可 点击此处 进行查看&＃xff01;具体代码以及其他内容可 点击此处 进行查看&＃xff01;

这个题是一个中等难度&＃xff0c;做起来挺快乐的&＃xff0c;就是对我而言时间成本有点高&＃xff0c;害&＃xff01;正文开始&＃xff01;

1、题目描述

有关题目描述就自己看图片吧

2、解决思路

2.1 排序 &＃43; 最大值

2.1.1 思路

简单说就是先将目标数组数据进行排序&＃xff0c;再对排序后的数组设定两个初值&＃xff0c;比如start、end&＃xff0c;其中start是寻找满足要求的区间的左值&＃xff0c;end是寻找满足要求的右值&＃xff0c;通过与目标区间的左右值进行比较来确定start与end&＃xff0c;即比如若end处于目标区间的范围内&＃xff0c;则将该区间的右值赋给end&＃xff0c;直至当end小于一个区间的左值&＃xff0c;然后将其插入到指定数组中即可。具体可见于代码&＃xff01;

2.1.2 程序代码

#include
#include
using namespace std;
#includevoid shownums(vector<vector<int>>& nums)
{for (int i &＃61; 0; i < nums.size(); i&＃43;&＃43;){int j &＃61; 0;cout << "[";for (; j < nums[0].size()-1; j&＃43;&＃43;){cout << nums[i][j] << " ";}cout << nums[i][j] << "] ";}cout << endl;
}vector<vector<int>> merge(vector<vector<int>>& intervals)
{int n &＃61; intervals.size();if (n <&＃61; 1)return intervals;sort(intervals.begin(), intervals.end());vector<vector<int>> ans;int start &＃61; intervals[0][0], end &＃61; intervals[0][1];int i;for (i &＃61; 1; i < intervals.size(); i&＃43;&＃43;){if (intervals[i][0] > end){ans.push_back({ start, end });start &＃61; intervals[i][0], end &＃61; intervals[i][1];}else if (intervals[i][1] >&＃61; end){end &＃61; intervals[i][1];}}if (i &＃61;&＃61; n)ans.push_back({ start, end });return ans;
}void test()
{/*vector> nums &＃61; { { 1, 3 }, { 2, 4 }, { 3, 6 }, {7,8} };*/vector<vector<int>> nums &＃61; { { 0, 3 }, { 0, 1 }, { 0, 2 }, { 1, 9 }, { 2, 5 }, { 10, 11 }, { 12, 20 }, { 19, 20 } };cout << "原数组&＃xff1a;";shownums(nums); cout << endl;cout << "处理后&＃xff1a;";shownums(merge(nums)); cout << endl;
}int main()
{test();system("pause");return 0;
}


2.1.3 运行结果

2.2 其他方法

若后续有时间或者有想法&＃xff0c;则补充其他方法&＃xff01;

3、总结

本次这个题难度还行&＃xff0c;只不过我浪费了好些时间&＃xff0c;但最终还是解决了它&＃xff0c;希望后面遇到同类型的题能有更快更好的解决思路或方法&＃xff01;