C++求非重叠区间的最大值 |21xrx.com

C++求非重叠区间的最大值

2023-06-23 10:04:34 深夜i -- --

C++ 非重叠区间最大值

C++是一种强大的编程语言，它提供了丰富的数据结构和算法，使得我们可以轻松解决各种复杂的问题。其中，求非重叠区间的最大值是一种常见的问题，下面我们就来讲一讲如何用C++实现这个算法。

首先，我们需要定义一个结构体Interval来表示区间，包括起始位置start和结束位置end。然后，我们可以将所有的区间按照结束位置从小到大排序，这样就可以确保每个区间的结束位置都在后面。

接着，我们使用一个变量last来表示当前非重叠区间的结束位置。遍历所有的区间，如果当前区间的起始位置大于last，那么这个区间就可以和前面的区间合并成一个非重叠区间，我们更新last为这个区间的结束位置。否则，这个区间就不能和前面的区间合并，我们继续向后遍历下一个区间。

最后，我们返回last作为最大的非重叠区间的结束位置即可。

下面是具体的代码实现：


struct Interval {
  int start;
  int end;
  Interval() : start(0), end(0) {}
  Interval(int s, int e) : start(s), end(e) {}
};
bool cmp(const Interval& a, const Interval& b)
  return a.end < b.end;
int maxNonOverlap(vector<Interval>& intervals) {
  int n = intervals.size();
  if (n == 0) return 0;
  sort(intervals.begin(), intervals.end(), cmp);
  int last = intervals[0].end;
  int count = 1;
  for (int i = 1; i < n; i++) {
    if (intervals[i].start >= last) {
      last = intervals[i].end;
      count++;
    }
  }
  return count;
}

在main函数中，我们可以输入区间的起始位置和结束位置，并存储在一个vector 中，然后调用maxNonOverlap函数来求最大的非重叠区间的长度。


int main() {
  int n;
  cin >> n;
  vector<Interval> intervals(n);
  for (int i = 0; i < n; i++) {
    int s, e;
    cin >> s >> e;
    intervals[i] = Interval(s, e);
  }
  int count = maxNonOverlap(intervals);
  cout << count;
  return 0;
}

综上所述，求非重叠区间的最大值是一个常见的问题，在C++中我们可以使用排序和贪心算法来解决。以上是一个简单的实现示例，当然也可以使用其他的方法。希望这篇文章能对大家有所帮助。

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

下一篇: C++读取JPG图片

评论区

()

相似文章