โปรแกรม C++ หาส่วนตัดร่วมของช่วงทั้งหมด (Intervals)

สมมติว่าเรามี N ช่วงในรูปแบบ {L, R} L คือเวลาเริ่มต้น และ R คือเวลาสิ้นสุด เราต้องหาส่วนตัดร่วมของทุกช่วง ส่วนตัดร่วมคือช่วงที่อยู่ภายในช่วงที่กำหนดทั้งหมด หากไม่พบ ให้คืนค่า -1 ตัวอย่างเช่น ถ้าช่วงเป็น [{1, 6}, {2, 8}, {3, 10}, {5, 8}] ช่วงผลลัพธ์คือ {5, 6}

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• พิจารณาช่วงแรกเป็นช่วงสุดท้าย
• เริ่มจากช่วงที่สอง พยายามค้นหาส่วนตัดร่วม สองกรณีอาจเกิดขึ้น:
  • ไม่มีส่วนตัดร่วมระหว่าง [L1, R1] และ [L2, R2] เกิดขึ้นได้ก็ต่อเมื่อ R1 < L2 หรือ R2 < L1 ในกรณีนี้คำตอบจะเป็น 0
  • มีส่วนตัดร่วมระหว่าง [L1, R1] และ [L2, R2] ส่วนตัดร่วมที่ต้องการจะเป็น {max(L1, L2), min(R1, R2)}

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

#include <iostream>
#include <algorithm>
using namespace std;

class interval{
public:
    int left, right;
};

void findIntersection(interval intervals[], int N) {
    int l = intervals[0].left;
    int r = intervals[0].right;
    for (int i = 1; i < N; i++) {
        if (intervals[i].left > r || intervals[i].right < l) {
            cout << -1;
            return;
        } else {
            l = max(l, intervals[i].left);
            r = min(r, intervals[i].right);
        }
    }
    cout << "{" << l << ", " << r << "}";
}

int main() {
    interval intervals[] = {{ 1, 6 }, { 2, 8 }, { 3, 10 }, { 5, 8 } };
    int N = sizeof(intervals) / sizeof(intervals[0]);
    findIntersection(intervals, N);
}

ผลลัพธ์

{5, 6}