12.30 - 合并区间 C++中class和C语言中struct的区别

目录

1.合并区间

a.核心思想

b.思路

c.步骤

2.C++中class和C语言中struct的区别

1.合并区间

56. 合并区间 - 力扣（LeetCode）https://leetcode.cn/problems/merge-intervals/

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { // 如果区间数组为空，直接返回空数组 if (intervals.empty()) return {}; // 按照区间的起始点进行排序 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; }); vector<vector<int>> res; res.push_back(intervals[0]); for (int i = 1; i < intervals.size(); ++i) { // 如果当前区间的起始点小于等于结果数组中最后一个区间的结束点，进行合并 if (intervals[i][0] <= res.back()[1]) { res.back()[1] = max(res.back()[1], intervals[i][1]); } // 否则，将当前区间加入结果数组 else { res.push_back(intervals[i]); } } return res; } };

a.核心思想

利用排序和合并的思路，先将所有区间按照起始点进行排序，然后依次遍历这些区间，将重叠的区间合并。

b.思路

① 对给定的区间数组按照每个区间的起始点进行升序排序。

② 初始化一个结果数组，将第一个区间放入结果数组。

③ 从第二个区间开始遍历，比较当前区间的起始点和结果数组中最后一个区间的结束点：

• 如果当前区间的起始点小于等于结果数组中最后一个区间的结束点，说明有重叠，更新结果数组中最后一个区间的结束点为两者结束点的较大值。

• 否则，将当前区间直接加入结果数组。

c.步骤

① 使用sort函数对区间数组进行排序。

② 创建结果数组res，并将排序后的第一个区间加入res。

③ 遍历排序后的区间数组，从第二个区间开始，按照上述思路进行合并操作。

④ 返回结果数组res。

2.C++中class和C语言中struct的区别

希望这些内容对大家有所帮助！

感谢大家的三连支持！