Khoảng thời gian chứa trong C ++

Giả sử chúng ta có một danh sách hai chiều các khoảng trong đó mỗi khoảng có hai giá trị [bắt đầu, kết thúc]. Chúng ta phải tìm xem có khoảng nào chứa khoảng khác không.

Vì vậy, nếu đầu vào là [[2,4], [5,11], [5,9], [10,10]], thì đầu ra sẽ đúng vì [5,11] chứa [5, 9].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp mảng v

• Xác định một mảng 2D ret

• cho mỗi khoảng thời gian nó trong v -

  • nếu ret trống, thì -

    • chèn nó vào cuối ret

  • ngược lại khi phần tử cuối cùng của ret> =it [0], thì -

    • trả về true

  • Nếu không

    • chèn nó vào cuối ret

• trả về false

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool static cmp(vector<int> &a, vector<int> &b) {
      return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
   }
   bool solve(vector<vector<int>> &v) {
      sort(v.begin(), v.end(), cmp);
      vector<vector<int>> ret;
      for (auto &it : v) {
         if (ret.empty())
         ret.push_back(it);
         else if (ret.back()[0] >= it[0])
         return true;
         else
         ret.push_back(it);
      }
      return false;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
   cout << (ob.solve(v));
}

Đầu vào

{{2,4},{5,11},{5,9},{10,10}}

Đầu ra

1