Interview Question | Merge Intervals Problem| Array | C++
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==1)
return intervals;
vector<pair<int,int>> p;
for(int i=0;i<intervals.size();i++)
{
p.push_back({intervals[i][0],intervals[i][1]});
}
sort(p.begin(),p.end());
vector<vector<int>> ans;
int f=p[0].first,s=p[0].second;
for(int i=0;i<p.size()-1;i++)
{
vector<int> a(2);
if(s>=p[i+1].first)
{
s=max(s,p[i+1].second);
}
else
{
a[0]=f;
a[1]=s;
f=p[i+1].first;
s=p[i+1].second;
ans.push_back(a);
}
}
int n=intervals.size();
ans.push_back({f,s});
return ans;
}
};English :
This C++ code defines a class Solution with a public member function merge that takes a vector of intervals represented as vectors of integers and merges overlapping intervals. The intervals are assumed to be in the form of [start, end] pairs. The merged intervals are returned as a vector of vectors.
Let’s break down the code step by step:
Check if there is only one interval in the input. If so, there is nothing to merge, and the original vector is returned.
if (intervals.size() == 1)
return intervals;Convert the input vector of vectors intervals into a vector of pairs p where each pair represents an interval's start and end.
vector<pair<int, int>> p;
for (int i = 0; i < intervals.size(); i++) {
p.push_back({intervals[i][0], intervals[i][1]});
}Sort the vector of pairs based on the starting values of the intervals.
sort(p.begin(), p.end());Initialize an empty vector ans to store the merged intervals. Use variables f and s to keep track of the current merged interval's start and end.
vector<vector<int>> ans;
int f = p[0].first, s = p[0].second;Iterate through the sorted pairs and merge overlapping intervals.
for (int i = 0; i < p.size() - 1; i++) {
vector<int> a(2);
if (s >= p[i + 1].first) {
// If the current interval overlaps with the next one, update the end.
s = max(s, p[i + 1].second);
} else {
// If no overlap, push the current merged interval and update for the next one.
a[0] = f;
a[1] = s;
f = p[i + 1].first;
s = p[i + 1].second;
ans.push_back(a);
}
}After the loop, push the last merged interval into the result vector.
ans.push_back({f, s});Return the final vector of merged intervals.
return ans;In summary, this code takes a vector of intervals, merges overlapping intervals, and returns the result as a new vector of intervals.
Hindi :
यह C++ कोड एक कक्षा Solution को परिभाषित करता है जिसमें एक सार्वजनिक सदस्य कार्य merge है जो एक पूर्णांकों के वेक्टर का समर्थन करता है और अवर्लैप होने वाले अंतरालों को मर्ज करता है। यह माना जाता है कि अंतराल [प्रारंभ, समाप्त] जोड़ीयों के रूप में हैं। मर्ज हुए अंतरालों को एक वेक्टर के रूप में लौटाया जाता है।
चलो कदम से इस कोड को विश्लेषण करें:
यह जांचता है कि इनपुट में केवल एक अंतराल है या नहीं। यदि हाँ, तो कोई मर्ज करने की आवश्यकता नहीं है, और मूल वेक्टर लौटाया जाता है।
if (intervals.size() == 1)
return intervals;इनपुट वेक्टर intervals को जोड़ीयों के प्रारंभ और समाप्त को दर्शाने वाले जोड़ों के वेक्टर में परिवर्तित करता है।
vector<pair<int, int>> p;
for (int i = 0; i < intervals.size(); i++) {
p.push_back({intervals[i][0], intervals[i][1]});
}जोड़ों के प्रारंभ मूल्यों के आधार पर जोड़ों के जोड़ों को क्रमबद्ध करता है।
sort(p.begin(), p.end());मर्ज हुए अंतरालों को स्टोर करने के लिए एक खाली वेक्टर ans को प्रारंभ करें। वर्तमान मर्ज हुए अंतराल की प्रारंभ और समाप्त को ट्रैक करने के लिए f और s उपयोग करें।
vector<vector<int>> ans;
int f = p[0].first, s = p[0].second;क्रमबद्ध जोड़ों के माध्यम से चलने और ओवरलैपिंग अंतरालों को मर्ज करने के लिए।
for (int i = 0; i < p.size() - 1; i++) {
vector<int> a(2);
if (s >= p[i + 1].first) {
// यदि वर्तमान अंतराल अगले के साथ ओवरलैप करता है, तो समाप्त को अपडेट करें।
s = max(s, p[i + 1].second);
} else {
// यदि कोई ओवरलैप नहीं है, तो वर्तमान मर्ज हुए अंतराल को पुश करें और अगले के लिए अपडेट करें।
a[0] = f;
a[1] = s;
f = p[i + 1].first;
s = p[i + 1].second;
ans.push_back(a);
}
}लूप के बाद, आखिरी मर्ज हुए अंतराल को परिणाम वेक्टर में पुश करें।
ans.push_back({f, s});अंत में, मर्ज हुए अंतरालों का अंतिम वेक्टर को लौटाएं।
return ans;संक्षेप में, यह कोड एक वेक्टर अंतरालों को लेता है, ओवरलैपिंग अंतरालों को मर्ज करता है, और परिणाम को एक नए वेक्टर अंतरालों के रूप में लौटाता है।
Hinglish :
Yeh C++ ka code ek class Solution ko define karta hai jismein ek public member function merge hai jo ek vector of intervals ko lekar overlapping intervals ko merge karta hai. Intervals ko assume kiya gaya hai [start, end] pairs ke roop mein hain. Merged intervals ko ek vector of vectors ke roop mein return kiya jata hai.
Chaliye ise kadam se kadam dekhe:
Check karta hai ki input mein sirf ek interval hai ya nahi. Agar hai, to kuch merge karne ki zarurat nahi hai, aur original vector ko return kiya jata hai
if (intervals.size() == 1)
return intervals;Convert karta hai input vector of vectors intervals ko ek vector of pairs p mein, jahan har pair ek interval ka start aur end represent karta hai.
vector<pair<int, int>> p;
for (int i = 0; i < intervals.size(); i++) {
p.push_back({intervals[i][0], intervals[i][1]});
}Sort karta hai pairs ko starting values ke basis par.
sort(p.begin(), p.end());Ek empty vector ans ko initialize karta hai merged intervals ko store karne ke liye. Variables f aur s ka istemal karke current merged interval ka start aur end track karne ke liye.
vector<vector<int>> ans;
int f = p[0].first, s = p[0].second;Sorted pairs par iterate karta hai aur overlapping intervals ko merge karta hai.
for (int i = 0; i < p.size() - 1; i++) {
vector<int> a(2);
if (s >= p[i + 1].first) {
// Agar current interval next ke saath overlap karta hai, to end ko update karta hai.
s = max(s, p[i + 1].second);
} else {
// Agar koi overlap nahi hai, to current merged interval ko push karta hai aur next ke liye update karta hai.
a[0] = f;
a[1] = s;
f = p[i + 1].first;
s = p[i + 1].second;
ans.push_back(a);
}
}Loop ke baad, last merged interval ko result vector mein push karta hai
ans.push_back({f, s});Final vector of merged intervals ko return karta hai.
return ans;Saransh mein, yeh code ek vector of intervals le leta hai, overlapping intervals ko merge karta hai, aur result ko ek naye vector of intervals ke roop mein return karta hai.
