C++ में इंटरवल सूचियों का इंटरसेक्शन

मान लीजिए हमारे पास क्लोज्ड इंटरवल्स की दो सूचियाँ हैं, जहाँ प्रत्येक सूची में इंटरवल्स परस्पर असंयुक्त (pairwise disjoint) हैं और सॉर्टेड क्रम में हैं। हमें इन दो इंटरवल सूचियों का इंटरसेक्शन (अंतर्व्यापन) निकालना है।

हम जानते हैं कि क्लोज्ड इंटरवल [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. while i < A.size() और j < B.size() लूप चलाएँ:
   • यदि 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 बढ़ाएँ।
     • यदि B[j][0] > B[j][1] या B[j][1] ≤ temp[0], तो j बढ़ाएँ।
     • temp को परिणाम में जोड़ें।
     • अगले इटरेशन के लिए continue करें।
   • यदि A[i][0] > B[j][1], तो j बढ़ाएँ, अन्यथा i बढ़ाएँ।

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

// टेस्ट
int main() {
    Solution ob;
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,27}};
    auto res = ob.intervalIntersection(A, B);
    for (auto& v : res) cout << "[" << v[0] << "," << v[1] << "] ";
    return 0;
}

इनपुट

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

आउटपुट

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