C++实现合并区间 |21xrx.com

C++实现合并区间

2023-06-29 19:41:16 深夜i -- --

合并区间 C++ 算法

合并区间是一种经典的算法问题，在许多领域都有广泛的应用。合并区间旨在将给定的一些不重叠的区间合并成为尽可能多的区间。

C++是一种流行的编程语言，拥有强大的算法和数据结构支持，是解决合并区间问题的优秀选择之一。下面我们来介绍如何使用C++实现合并区间。

首先，我们需要定义一个区间类，它包含左端点和右端点两个属性。代码实现如下：


class Interval {
public:
  int start;
  int end;
  Interval() : start(0), end(0) {}
  Interval(int s, int e) : start(s), end(e) {}
};

接下来，我们可以使用STL中的sort函数对区间数组进行排序，以便于后续的扫描合并。排序的关键字是区间的左端点。代码实现如下：


bool cmp(const Interval& a, const Interval& b)
  return a.start < b.start;
sort(intervals.begin(), intervals.end(), cmp);

然后，我们可以使用双指针的方法，从左到右扫描区间数组。如果相邻的两个区间有重叠部分，则将它们合并成一个。合并后的新区间的右端点是两个被合并的区间的右端点中的较大者。代码实现如下：


vector<Interval> merge(vector<Interval>& intervals) {
  if (intervals.size() <= 1) return intervals;
  sort(intervals.begin(), intervals.end(), cmp);
  vector<Interval> res;
  int left = intervals[0].start, right = intervals[0].end;
  for (int i = 1; i < intervals.size(); i++) {
    if (intervals[i].start <= right) {
      right = max(right, intervals[i].end);
    } else {
      res.push_back(Interval(left, right));
      left = intervals[i].start;
      right = intervals[i].end;
    }
  }
  res.push_back(Interval(left, right));
  return res;
}

最后，我们将合并后的新区间存入一个新的数组中，并返回该数组即可。

使用C++实现合并区间的过程相对简单，但是需要注意一些细节问题，例如区间比较函数的写法、排序函数的调用、双指针的迭代方式等。通过不断地练习和实践，我们可以更加熟练地运用C++来解决各种算法问题。

上一篇: idea打包java可执行jar包

下一篇: "C++实现的三个特效"

评论区

()

相似文章