Kiểm tra xem có bất kỳ hai khoảng nào trùng nhau trong một tập hợp các khoảng nhất định trong C ++ hay không

Giả sử, chúng ta được cung cấp một tập hợp các khoảng thời gian bao gồm các giá trị (time1, time2) trong đó time1 đại diện cho thời gian bắt đầu và time2 đại diện cho thời gian kết thúc của một sự kiện. Nhiệm vụ của chúng ta là kiểm tra xem có bất kỳ khoảng nào trong số này trùng lặp với bất kỳ khoảng nào khác trong tập hợp này hay không. Nếu bất kỳ khoảng nào trùng nhau, chúng tôi trả về kết quả là Đúng, nếu không, chúng tôi trả về Sai.

Vì vậy, nếu đầu vào là [(4,7), (5,11), (7,11), (5,8)] thì đầu ra sẽ là True.

Để 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 danh sách đầu vàoArr
• đối với tôi trong phạm vi từ 1 đến kích thước của inputArr, hãy thực hiện
  • nếu inputArr [i - 1] .time2> inputArr [i] .time1 thì
    • trả về True
  • trả về Sai

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 IntervalClass {
public:
   int time1, time2;
};
bool compare(IntervalClass inst1, IntervalClass inst2){
   return (inst1.time1 < inst2.time1) ? true : false;
}
bool solve(vector<IntervalClass> &inputArr){
   int size = inputArr.size();
   sort(inputArr.begin(), inputArr.end(), compare);
   for (int i = 1; i < size; i++)
      if (inputArr[i - 1].time2 > inputArr[i].time1)
         return true;
   return false;
}
int main(){
   vector<IntervalClass> inputArr = {{4,7},{5,11},{7,11},{5,8}};
   int size = sizeof(inputArr) / sizeof(inputArr[0]);
   cout << solve(inputArr);
}

Đầu vào

{{4,7},{5,11},{7,11},{5,8}}

Đầu ra

1