รวมช่วงเวลาที่ทับซ้อนกัน (Merge Overlapping Intervals) ด้วย C++

ข้อความโจทย์

กำหนดชุดของช่วงเวลา (Time Intervals) ในลำดับใดก็ได้ ให้รวมช่วงเวลาที่ทับซ้อนกันทั้งหมดเป็นช่วงเดียว และแสดงผลลัพธ์ที่ควรมีเฉพาะช่วงเวลาที่ไม่ทับซ้อนกัน (Mutually Exclusive Intervals)

ชุดช่วงเวลาที่กำหนดคือ {{12, 14}, {11, 13}, {20, 22}, {21, 23}} แล้ว

• ช่วง {12, 14} และ {11, 13} ทับซ้อนกัน จึงรวมเป็น {11, 14}
• ช่วง {20, 22} และ {21, 23} ทับซ้อนกัน จึงรวมเป็น {20, 23}

อัลกอริทึม

1. เรียงลำดับช่วงเวลาตามลำดับเพิ่มขึ้นของเวลาเริ่มต้น
2. ใส่ช่วงเวลาแรกลงในสแต็ก (Stack)
3. สำหรับแต่ละช่วงเวลา ทำขั้นตอนต่อไปนี้:
   3.1. ถ้าช่วงเวลาปัจจุบันไม่ทับซ้อนกับยอดสแต็ก ให้ Push เข้าไป
   3.2. ถ้าช่วงเวลาปัจจุบันทับซ้อนกับยอดสแต็ก และเวลาสิ้นสุดของช่วงปัจจุบันมากกว่ายอดสแต็ก ให้อัปเดตยอดสแต็กด้วยเวลาสิ้นสุดของช่วงปัจจุบัน
4. สุดท้าย สแต็กจะมีช่วงเวลาที่รวมแล้ว

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

#include <iostream>
#include <algorithm>
#include <stack>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

struct interval {
    int start;
    int end;
};

bool compareInterval(interval i1, interval i2) {
    return (i1.start < i2.start);
}

void mergeOverlappingIntervals(interval *arr, int n) {
    if (n <= 0) {
        return;
    }
    stack<interval> s;
    sort(arr, arr + n, compareInterval);
    s.push(arr[0]);
    for (int i = 1; i < n; ++i) {
        interval top = s.top();
        if (top.end < arr[i].start) {
            s.push(arr[i]);
        } else if (top.end < arr[i].end) {
            top.end = arr[i].end;
            s.pop();
            s.push(top);
        }
    }
    cout << "Merged intervals: " << endl;
    while (!s.empty()) {
        interval i = s.top();
        cout << "{" << i.start << ", " << i.end << "}" << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    interval arr[] = {{12, 14}, {11, 13}, {20, 22}, {21, 23}};
    mergeOverlappingIntervals(arr, SIZE(arr));
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Merged intervals: {20, 23} {11, 14}