21xrx.com
2024-12-22 21:23:43 Sunday
登录
文章检索 我的文章 写文章
合并重叠区间：C++实现
2023-07-09 20:06:51 深夜i     --     --
合并区间 重叠 C++ 算法实现 排序

重叠区间是指在数轴上存在交集的区间。比如说，[1,3]和[2,5]就是重叠区间，因为它们在数轴上有交集[2,3]。对于一组区间，我们需要将其中重叠的区间合并成新的区间，以便更好地管理和处理。本文将讨论如何在C++中实现合并重叠区间的算法。

一、问题描述

给定一组n个区间，每个区间用一对左右端点表示，即[a1,b1],[a2,b2],...,[an,bn]，保证每个ai≤bi。请将重叠的区间合并成不重叠的区间。

二、解决方法

1.算法思路

首先对所有的区间按照左端点从小到大进行排序，然后对于相邻的两个区间[a1,b1]和[a2,b2]，如果有重叠部分则将其合并成一个区间[c,d]，其中c=min(a1,a2)，d=max(b1,b2)，并将其加入结果集合。重复进行这个过程直到所有区间都被遍历过。

2.代码实现

C++代码实现如下：



#include<iostream>


#include<algorithm>


#include<vector>


using namespace std;


struct Interval{


  int start;


  int end;


  Interval(int s, int e) : start(s), end(e) {}


};


bool mycomp(Interval a, Interval b)


  return a.start < b.start;


vector<Interval> merge(vector<Interval>& intervals) {


  sort(intervals.begin(), intervals.end(), mycomp);


  vector<Interval> res;


  int len = intervals.size();


  int i = 0;


  while (i < len){


    int j = i + 1;


    int end = intervals[i].end;


    while (j < len && intervals[j].start <= end){


      end = max(end, intervals[j].end);


      j++;


    }


    res.push_back(Interval(intervals[i].start, end));


    i = j;


  }


  return res; 


}


int main(){


  vector<Interval> intervals;


  intervals.push_back(Interval(1,3));


  intervals.push_back(Interval(2,6));


  intervals.push_back(Interval(8,10));


  intervals.push_back(Interval(15,18));


  vector<Interval> res = merge(intervals);


  for (int i = 0; i < res.size(); i++){


    cout << "[" << res[i].start << "," << res[i].end << "]" << " ";


  }


  cout << endl;


  return 0;


}

首先定义了一个结构体Interval表示区间，重载了 Interval 上的运算符>=，然后又定义了一个比较函数mycomp，用于排序。函数merge中，首先将所有区间按照左端点从小到大进行排序，然后依次遍历区间，比较相邻的两个区间是否有重叠部分，并在有重叠部分时将其合并成一个区间加入结果集res中。

三、总结

本文讨论了如何在C++中实现合并重叠区间的算法。我们可以将所有区间按照左端点从小到大进行排序，然后依次遍历区间，比较相邻的两个区间是否有重叠部分，并在有重叠部分时将其合并成一个区间加入结果集。这个算法时间复杂度为O(nlogn)，空间复杂度为O(n)。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复