ตรวจสอบช่วงเวลาที่ทับซ้อนกันในชุดช่วงเวลาด้วย C++

สมมติว่าเราได้รับชุดของช่วงเวลา (intervals) ที่ประกอบด้วยค่า (time1, time2) โดย time1 แทนเวลาเริ่มต้น และ time2 แทนเวลาสิ้นสุดของเหตุการณ์หนึ่ง ภารกิจคือตรวจสอบว่าช่วงเวลาใดช่วงเวลาหนึ่งทับซ้อน (overlap) กับช่วงเวลาอื่นในชุดนี้หรือไม่ ถ้ามีการทับซ้อน คืนค่า True มิฉะนั้นคืนค่า False

เช่น ถ้าอินพุตคือ [(4,7), (5,11), (7,11), (5,8)] ผลลัพธ์จะเป็น True

วิธีแก้ปัญหา:

• เรียงลำดับลิสต์ inputArr
• ลูป i จาก 1 ถึงขนาดของ inputArr:
  • ถ้า inputArr[i-1].time2 > inputArr[i].time1 คืนค่า True
• คืนค่า False

ตัวอย่างโค้ด

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

Input

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

Output

1