C++-এ ইন্টারভাল লিস্ট ইন্টারসেকশন (Interval List Intersections)

দুটি ক্লোজড ইন্টারভালের লিস্ট দেওয়া থাকলে, যেখানে প্রতিটি লিস্টের ইন্টারভালগুলো পেয়ারওয়াইজ ডিজয়েন্ট (পরস্পর বিচ্ছিন্ন) এবং সর্টেড অর্ডারে থাকে। আমাদের কাজ হল এই দুটি ইন্টারভাল লিস্টের ইন্টারসেকশন (সর্বনিম্ন সাধারণ অংশ) বের করা।

ক্লোজড ইন্টারভাল [a, b] মানে a <= b এবং এটি বোঝায় a <= x <= b এমন সকল বাস্তব সংখ্যা x। দুটি ক্লোজড ইন্টারভালের ইন্টারসেকশন হয় একটি বাস্তব সংখ্যার সেট যা হয় খালি বা আবার একটি ক্লোজড ইন্টারভাল হিসেবে প্রকাশ করা যায়।

উদাহরণ

ইনপুট: 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]]

সমাধানের পদ্ধতি

একটি রেজাল্ট লিস্ট res তৈরি করুন, ইনডেক্স i := 0 এবং j := 0 সেট করুন।
intersect() নামে একটি মেথড ডিফাইন করুন যা দুটি ইন্টারভাল a এবং b নেবে:
- যদি a[0] <= b[0] এবং a[1] >= b[0] হয়, তবে true রিটার্ন করুন।
- অথবা b[0] <= a[0] এবং b[1] >= a[0] হয়, তবে true রিটার্ন করুন।
- অন্যথায় false রিটার্ন করুন।
যখন 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++
  - res.push_back(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;
    }
};

ইনপুট

[[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]]