การหาช่วงตัดของรายการช่วงใน C++

การหาช่วงตัดของรายการช่วง (Interval List Intersections)

สมมติว่าเรามีสองรายการของช่วงปิด (closed intervals) โดยแต่ละรายการมีช่วงที่ไม่ทับซ้อนกัน (pairwise disjoint) และเรียงลำดับแล้ว เราต้องการหาช่วงตัด (intersection) ของสองรายการช่วงนี้

ช่วงปิด [a, b] หมายถึง a ≤ b คือเซตของจำนวนจริง x ที่ทำให้ a ≤ x ≤ b ช่วงตัดของช่วงปิดสองช่วงจะเป็นเซตของจำนวนจริงที่อาจว่างเปล่าหรือสามารถแทนเป็นช่วงปิดได้

ตัวอย่างเช่น หากอินพุทคือ A = [[0,2],[5,10],[13,23],[24,25]] และ B = [[1,5],[8,12],[15,24],[25,27]] ผลลัพธ์จะเป็น [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

ขั้นตอนการแก้ปัญหา

1. สร้างรายการผลลัพธ์ res กำหนด i := 0 และ j := 0
2. กำหนดฟังก์ชัน intersect() ที่รับพารามิเตอร์ a และ b:
   • ถ้า a[0] ≤ b[0] และ a[1] ≥ b[0] คืนค่า true
   • ถ้า b[0] ≤ a[0] และ b[1] ≥ a[0] คืนค่า true
   • มิฉะนั้นคืนค่า false
3. วนลูปในขณะที่ i < size of A และ j < size of B:
   • ถ้า intersect(A[i], B[j]) เป็นจริง:
     • คำนวณ temp := [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]
     • อัปเดต A[i][0] := temp[1] + 1, B[j][0] := temp[1] + 1
     • ถ้า A[i][0] > A[i][1] หรือ A[i][1] ≤ temp[0] เพิ่ม i ขึ้น 1
     • ถ้า B[j][0] > B[j][1] หรือ B[j][1] ≤ temp[0] เพิ่ม j ขึ้น 1
     • เพิ่ม temp เข้า result
     • ข้ามไปรอบถัดไป (continue)
   • ถ้า A[i][0] > B[j][1] เพิ่ม j ขึ้น 1 มิฉะนั้นเพิ่ม i ขึ้น 1

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

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        while (i < A.size() && j < B.size()) {
            if (intersect(A[i], B[j])) {
                vector<int> temp = {max(A[i][0], B[j][0]), min(A[i][1], B[j][1])};
                A[i][0] = temp[1] + 1;
                B[j][0] = temp[1] + 1;
                if (A[i][0] > A[i][1] || A[i][1] <= temp[0]) i++;
                if (B[j][0] > B[j][1] || B[j][1] <= temp[0]) j++;
                result.push_back(temp);
                continue;
            }
            if (A[i][0] > B[j][1]) j++;
            else i++;
        }
        return result;
    }
    
    bool intersect(vector<int>& a, vector<int>& b) {
        if (a[0] <= b[0] && a[1] >= b[0]) return true;
        if (b[0] <= a[0] && b[1] >= a[0]) return true;
        return false;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [[0,2],[5,10],[13,23],[24,25]] [[1,5],[8,12],[15,24],[25,27]]

Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]