C++ में इंटरवल डालना

मान लीजिए हमारे पास नॉन-ओवरलैपिंग इंटरवल्स का एक सेट है; हमें एक नया इंटरवल इंटरवल्स में डालना है। यदि आवश्यक हो तो हम मर्ज कर सकते हैं। यदि इनपुट [[1,4],[6,9]] है, और नया इंटरवल [2,5] है, तो आउटपुट [[1,5],[6,9]] होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• नए इंटरवल को पिछले इंटरवल लिस्ट के अंत में डालें
• इंटरवल लिस्ट को इंटरवल्स के प्रारंभिक समय के आधार पर सॉर्ट करें, n := इंटरवल्स की संख्या
• ans नामक एक ऐरे बनाएं, पहला इंटरवल ans में डालें
• index := 1
• जब तक index < n:
  • last := ans का आकार - 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 को 1 बढ़ाएं
• ans वापस करें

उदाहरण (C++ कोड)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> 
using namespace std; 
void print_vector(vector<auto> v){ 
    cout << "["; 
    for(int i = 0; i < v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 
void print_vector(vector<vector<auto> > 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)); 
}

इनपुट

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

आउटपुट

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