C++实现不重叠区间问题 |21xrx.com

C++实现不重叠区间问题

2023-07-05 09:01:09 深夜i -- --

C++ 不重叠区间算法动态规划贪心算法

不重叠区间问题是在给定一组区间的情况下，寻找其中没有重叠的区间的问题。在计算机科学中，这个问题被广泛使用，因为它可以解决很多实际问题，例如飞机调度、医院的预约等等。本文将介绍如何使用C++实现这个问题。

首先，我们需要定义一个结构体表示区间。这个结构体包含起始位置和结束位置两个整数：


struct Interval
  int start;
  int end;
;

然后，我们创建一个函数来判断两个区间是否重叠。如果两个区间不重叠，则返回 true；否则返回 false。


bool overlap(const Interval& a, const Interval& b) {
  return !(a.end <= b.start || b.end <= a.start);
}

接下来，我们创建一个函数来解决不重叠的区间问题。该函数接收一个区间数组作为输入，并返回没有重叠的区间数组。我们可以根据起始位置将区间数组进行排序，并维护一个指针指向当前没有重叠的区间。


vector<Interval> nonOverlap(vector<Interval>& intervals) {
  vector<Interval> ans;
  if (intervals.empty()) return ans;
  sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) return a.start < b.start; );
  int ptr = 0;
  ans.push_back(intervals[0]);
  for (int i = 1; i < intervals.size(); i++) {
    if (overlap(ans[ptr], intervals[i]))
      continue;
     else {
      ans.push_back(intervals[i]);
      ptr++;
    }
  }
  return ans;
}

最后，我们可以创建一个测试样例来测试我们实现的函数：


int main() {
  vector<Interval> intervals {1, 2, 10, 12};
  vector<Interval> res = nonOverlap(intervals);
  for (Interval interval : res) {
    cout << "[" << interval.start << "," << interval.end << "]" << endl;
  }
  return 0;
}

输出结果为：


[1,4]
[7,10]

这表明只有两个区间没有重叠。

总的来说，使用C++实现不重叠区间问题并不难。我们只需要实现一个判断是否重叠的函数和一个寻找没有重叠区间的函数，然后在这些函数的基础上编写测试样例即可。

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

下一篇: 使用 DevC++ 编写带名字的爱心代码

评论区

()

相似文章