Các khoảng ngắt quãng tối đa trong C ++

Mô tả

Cho một tập hợp N khoảng, nhiệm vụ là tìm tập hợp lớn nhất của các khoảng rời nhau. Hai khoảng [i, j] &[k, l] được cho là rời rạc nếu chúng không có điểm chung nào

Nếu khoảng thời gian là {{10, 20} {23, 35}, {15, 21}, {37, 41}} thì các cặp rời rạc không chồng chéo tối đa là -

{10, 20}
{23, 35}
{37, 41}

Lưu ý rằng chúng tôi không thể bao gồm {15, 21} vì nó sẽ trùng lặp với {10, 20}

Thuật toán

1. Sort the intervals, with respect to their end points.
2. Traverse the all intervals, if we get two overlapping intervals, then choose the interval with lower end point. Choosing such interval will ensure that intervals further can be accommodated without any overlap
3. Repeat the same procedure for all the intervals and print all the intervals which satisfy these criteria

Ví dụ

#include <bits/stdc++.h>
using namespace std;
bool sortFun(pair<int, int> &a, pair<int, int> &b){
   return (a.second < b.second);
}
void getMaxDisjointInterval(vector<pair<int, int>> intervals){
   sort(intervals.begin(), intervals.end(), sortFun);
   cout << "{" << intervals[0].first << ", " << intervals[0].second << "}\n";
   int r1 = intervals[0].second;
   for (int i = 1; i < intervals.size(); ++i) {
      int l1 = intervals[i].first;
      int r2 = intervals[i].second;
      if (l1 > r1) {
         cout << "{" << l1 << ", " << r2 << "}\n";
         r1 = r2;
      }
   }
}
int main(){
   int n = 4;
   vector<pair<int, int>> intervals = {
      {10, 20},
      {23, 35},
      {15, 21},
      {37, 41}
   };
   cout << "Max disjoint pairs are:\n";
   getMaxDisjointInterval(intervals);
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Max disjoint pairs are:
{10, 20}
{23, 35}
{37, 41}