C++-এ ইন্টারভাল ইনসার্ট (Insert Interval)

ধরুন আমাদের কাছে ওভারল্যাপ না করা ইন্টারভালের একটি সেট আছে; আমাদের কাজ হল একটি নতুন ইন্টারভাল সেটে ইনসার্ট করা। প্রয়োজনে মার্জ (merge) করা যাবে। যেমন, ইনপুট [[1,4],[6,9]] এবং নতুন ইন্টারভাল [2,5] হলে আউটপুট হবে [[1,5],[6,9]]।

সমাধানের ধাপসমূহ:

• নতুন ইন্টারভালটি পূর্বের ইন্টারভাল লিস্টের শেষে যোগ করুন

• ইন্টারভাল লিস্টকে ইন্টারভালের শুরুকালিন সময় অনুযায়ী সর্ট করুন, n := ইন্টারভালের সংখ্যা

• ans নামে একটি অ্যারে তৈরি করুন, প্রথম ইন্টারভালটি ans-এ যোগ করুন

• index := 1

• যখন index < n:

  • last := ans.size() - 1

  • যদি max(ans[last][0], ans[last][1]) < min(intervals[index][0], intervals[index][1]) হয়, তবে intervals[index] ans-এ যোগ করুন

  • অন্যথায়: ans[last][0] = min(ans[last][0], intervals[index][0]), ans[last][1] = max(ans[last][1], intervals[index][1])

  • index++

• ans রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<vector<int> > v) { 
    cout << "["; 
    for(int i = 0; i < v.size(); i++) { 
        cout << "["; 
        for(int j = 0; j < v[i].size(); j++) { 
            cout << v[i][j] << ", "; 
        } 
        cout << "],"; 
    } 
    cout << "]" << endl; 
} 

class Solution { 
public: 
    static bool cmp(vector<int> a, vector<int> b) { 
        return a[0] < b[0]; 
    } 
    
    vector<vector<int> > insert(vector<vector<int> > &intervals, vector<int> &newInterval) { 
        intervals.push_back(newInterval); 
        sort(intervals.begin(), intervals.end(), cmp); 
        int n = intervals.size(); 
        vector<vector<int> > ans; 
        ans.push_back(intervals[0]); 
        int index = 1; 
        while(index < n) { 
            int last = ans.size() - 1; 
            if(max(ans[last][0], ans[last][1]) < min(intervals[index][0], intervals[index][1])) { 
                ans.push_back(intervals[index]); 
            } else { 
                ans[last][0] = min(ans[last][0], intervals[index][0]); 
                ans[last][1] = max(ans[last][1], intervals[index][1]); 
            } 
            index++; 
        } 
        return ans; 
    } 
}; 

int main() { 
    vector<vector<int> > v = {{1,4},{6,9}}; 
    vector<int> v1 = {2,5}; 
    Solution ob; 
    print_vector(ob.insert(v, v1)); 
    return 0;
}

ইনপুট

[[1,4],[6,9]] [2,5]

আউটপুট

[[1, 5, ],[6, 9, ],]