Kiểm tra xem có hai khoảng nào chồng chéo nhau trong tập hợp khoảng cho trước trong C++

Giả sử, chúng ta được cho một tập hợp các khoảng 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 chồng chéo lên khoảng khác trong tập hợp này hay không. Nếu bất kỳ khoảng nào chồng chéo, chúng ta trả về kết quả là True, ngược lại trả về False.

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

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

• Sắp xếp danh sách inputArr
• Với i từ 1 đến kích thước của inputArr, làm:
  • Nếu inputArr[i-1].time2 > inputArr[i].time1 thì:
    • Trả về True
• Trả về False

Ví dụ mã

#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);
    return 0;
}

Đầu vào

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

Đầu ra

1