《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（55）聚宝盆装区间 ...

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（55）聚宝盆装区间 - 归并区间（排序贪心）

哪吒在数据修仙界中继承他的修炼之旅。这一次，他来到了一片神秘的聚宝盆谷，谷中有一只巨大的聚宝盆，盆身闪烁着神秘的光芒。谷口有一块巨大的石碑，上面刻着一行笔墨：“欲装此盆，需以聚宝之力，归并区间，排序贪心显真身。”
哪吒定睛一看，石碑上另有一行小字：“区间[[1,3],[2,6],[8,10],[15,18]]归并后为[[1,6],[8,10],[15,18]]。”哪吒心中一动，他知道这是一道关于归并区间的难题，需要通过排序和贪心战略来办理。
暴力解法：聚宝盆的初次尝试

哪吒心想：“要归并区间，我可以逐个区间检查。”他催动聚宝盆之力，通过逐个区间比较，试图找到重叠或相邻的区间并归并。

1. vector<vector<int>> merge(vector<vector<int>>& intervals) {
2.    
3.     vector<vector<int>> result;
4.     if (intervals.empty()) return result;
5.     sort(intervals.begin(), intervals.end());
6.     vector<int> current = intervals[0];
7.     for (int i = 1; i < intervals.size(); ++i) {
8.    
9.         if (intervals[i][0] <= current[1]) {
10.    
11.             current[1] = max(current[1], intervals[i][1]);
12.         } else {
13.    
14.             result.push_back(current);
15.             current = intervals[i];
16.         }
17.     }
18.     result.push_back(current);
19.     return result;
20. }

复制代码

哪吒成功地归并了区间，但聚宝盆的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当区间数目很多时，灵力消耗巨大。
C++语法点

在C++中，归并区间问题涉及到排序和贪心战略。以下是一些重要特性：

• 排序：
  
     
  
  • 使用sort函数对区间按起始位置排序。   
    
  • 常用操作：
    
         
    
    • sort(intervals.begin(), intervals.end())：按区间起始位置排序。   
      
       
    
    
  
• 贪心战略：
  
     
  
  • 通过维护当前区间，渐渐归并重叠或相邻的区间。  
    
  
  

高阶优化：排序贪心的智慧

哪吒元神中忽然浮现金色铭文——「聚宝盆装区间，排序贪心显真身」。他意识到，可以通过排序和贪心战略优化区间归并过程。
哪吒决定使用排序和贪心战略，先按区间起始位置排序，然后维护一个当前区间，渐渐归并重叠或相邻的区间。通过这种方式，他成功地归并了全部区间，而且灵力消耗大幅减少。

1. vector<vector<int>> merge

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。