Interview Question: Merge Intervals Array C++
Company Interviews Using C++ Data Structures and Algorithms
#include <bits/stdc++.h>
/*
intervals[i][0] = start point of i'th interval
intervals[i][1] = finish point of i'th interval
*/
vector<vector<int>> mergeIntervals(vector<vector<int>> &intervals)
{
if(intervals.size()<=1) return intervals;
vector<vector<int>>output;
sort(intervals.begin(), intervals.end());
output.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (output.back()[1] >= intervals[i][0]) output.back()[1]= max(output.back()[1], intervals[i][1]);
else output.push_back(intervals[i]);
}
return output;
}English :
This C++ code defines a function called `mergeIntervals` that takes a vector of intervals as input and returns a vector of merged intervals. It uses the concept of merging overlapping intervals.
Here’s a breakdown of how the code works:
1. The code includes the C++ Standard Template Library header `<bits/stdc++.h>`, which is a commonly used header that includes many other headers in one. This code does not make use of any specific features from `<bits/stdc++.h>` and could work with the specific headers needed instead.
2. The function `mergeIntervals` takes a reference to a vector of vectors of integers as input. Each sub-vector inside the main vector represents an interval with two elements: `intervals[i][0]` represents the start point of the `i`-th interval, and `intervals[i][1]` represents the finish point of the `i`-th interval.
3. It checks if the number of intervals in the input vector is less than or equal to 1. If so, it returns the input vector as there’s no need to merge single intervals.
4. A vector called `output` is declared to store the merged intervals.
5. The `intervals` vector is sorted using the `sort` function. Sorting the intervals based on their start points ensures that overlapping intervals are adjacent to each other, making it easier to merge them.
6. The first interval (the smallest start point) is pushed into the `output` vector.
7. A `for` loop is used to iterate through the sorted intervals, starting from the second interval (index 1).
8. Within the loop, it checks if the finish point of the last interval in the `output` vector (accessed using `output.back()[1]`) is greater than or equal to the start point of the current interval being examined (`intervals[i][0]`).
- If there is an overlap, it updates the finish point of the last interval in the `output` vector to be the maximum of its current finish point and the finish point of the current interval (`output.back()[1] = max(output.back()[1], intervals[i][1]`).
— If there is no overlap, it means that the current interval does not overlap with the last interval in the `output` vector, so it pushes the current interval into the `output` vector.
9. After iterating through all intervals, the `output` vector contains the merged intervals, and it is returned as the result of the function.
In summary, this code takes a list of intervals, sorts them by their start points, and then merges overlapping intervals into a new list of merged intervals. This is a common algorithm for working with intervals in computer science and is often used in applications such as scheduling, time-series analysis, and more.
Hindi :
यह C++ कोड एक फ़ंक्शन `mergeIntervals` को परिभाषित करता है जो एक इंटरवल का एक वेक्टर द्वारा इनपुट लेता है और मर्ज किए गए इंटरवल का एक वेक्टर वापस देता है। यह ओवरलैपिंग इंटरवल्स को मर्ज करने के अवसर की अवधारणा का उपयोग करता है।
यहाँ कोड कैसे काम करता है, इसका एक विवरण है:
1. कोड में C++ स्टैंडर्ड टेम्पलेट लाइब्रेरी हेडर `<bits/stdc++.h>` शामिल है, जिसमें कई अन्य हेडर्स शामिल होते हैं। इस कोड में `<bits/stdc++.h>` से किसी विशेष विशेषताओं का उपयोग नहीं किया जाता है और इसके बजाय आवश्यक हेडर्स के साथ काम किया जा सकता है।
2. फ़ंक्शन `mergeIntervals` एक वेक्टर के रूप में इंटरवल्स का संदर्भ लेता है और उन्हें मर्ज किए गए इंटरवल्स के रूप में वापस देता है।
3. यह यह जांचता है कि इनपुट वेक्टर में इंटरवल की संख्या 1 के बराबर या उससे कम है। अगर हाँ, तो एकल इंटरवल को मर्ज करने की आवश्यकता नहीं है, इसलिए यह इनपुट वेक्टर को वापस देता है।
4. मर्ज किए गए इंटरवल्स को संग्रहित करने के लिए `output` नामक एक वेक्टर की परिभाषा की जाती है।
5. `intervals` वेक्टर को `sort` फ़ंक्शन का उपयोग करके क्रमबद्ध किया जाता है। उनके प्रारंभ बिंदुओं के आधार पर इंटरवल्स को क्रमबद्ध करने से यह सुनिश्चित होता है कि ओवरलैपिंग इंटरवल्स एक-दूसरे के पास होते हैं, जिससे उन्हें मर्ज करना आसान होता है।
6. पहला इंटरवल (सबसे छोटे प्रारंभ बिंदु) को `output` वेक्टर में डाल दिया जाता है।
7. `for` लूप का उपयोग क्रमबद्ध इंटरवल्स के माध्यम से करने के लिए किया जाता है, दूसरे इंटरवल (सूची 1 के इंडेक्स) से प्रारंभ करके।
8. इस लूप के भीतर, यह देखता है कि `output` वेक्टर में अंतिम इंटरवल के समापन बिंदु (उसका उपयोग `output.back()[1]` का उपयोग करके किया जाता है) वर्तमान जांची जाने वाले इंटरवल के प्रारंभ बिंदु (`intervals[i][0]`) के बराबर या उससे अधिक है।
- यदि ओवरलैप होता है, तो य
ह उसका समापन बिंदु अधिम समापन बिंदु और वर्तमान इंटरवल के समापन बिंदु के बीच का अधिकतम बनाता है (`output.back()[1] = max(output.back()[1], intervals[i][1]`).
— यदि कोई ओवरलैप नहीं होता है, तो यह इसका मतलब होता है कि वर्तमान इंटरवल पिछले इंटरवल के साथ ओवरलैप नहीं करता है, इसलिए यह वर्तमान इंटरवल को `output` वेक्टर में डालता है।
9. सभी इंटरवल्स के माध्यम से चलने के बाद, `output` वेक्टर में मर्ज किए गए इंटरवल्स होते हैं, और यह फ़ंक्शन के परिणाम के रूप में वापस दिया जाता है।
संक्षेप में, यह कोड एक इंटरवलों की सूची लेता है, उन्हें उनके प्रारंभ बिंदुओं के आधार पर क्रमबद्ध करता है, और फिर ओवरलैपिंग इंटरवलों को एक नई सूची में मर्ज करता है। यह कंप्यूटर विज्ञान में इंटरवलों के साथ काम करने के लिए एक सामान्य एल्गोरिथ्म है और इसका आमतौर पर अनुसंधान कार्यों, समय-श्रृंगार विश्लेषण आदि जैसे अनुप्रयोगों में उपयोग किया जाता है।
Hinglish :
Is C++ mein likhi code ek function `mergeIntervals` ko define karti hai jo input ke roop mein ek intervals ka vector leti hai aur usse merge kiye gaye intervals ka ek naya vector return karti hai. Is code mein overlapping intervals ko merge karne ka concept istemal kiya gaya hai.
Is code ka kaam karne ka tarika neeche diya gaya hai:
1. Is code mein C++ Standard Template Library header `<bits/stdc++.h>` ko include kiya gaya hai. Ye ek aam taur par istemal hone wala header hai jo kai aur headers ko ek saath include karta hai. Is code mein `<bits/stdc++.h>` se koi khaas feature istemal nahi hua hai aur specific headers ka istemal bhi kiya ja sakta tha.
2. Function `mergeIntervals` ek reference ke roop mein ek vector of vectors of integers ko input ke roop mein leti hai. Har sub-vector jo main vector ke andar hota hai, woh ek interval ko represent karta hai jisme do elements hote hain: `intervals[i][0]` us interval ki shuruaat point ko represent karta hai, aur `intervals[i][1]` us interval ki ant point ko represent karta hai.
3. Yeh check karta hai ki input vector mein intervals ki sankhya 1 ya usse kam hai ya nahi. Agar hai, to yeh input vector ko seedhe return kar deta hai kyun ki ek hi interval ko merge karne ki zaroorat nahi hoti.
4. Ek vector `output` ko declare kiya gaya hai jisme merge kiye gaye intervals ko store kiya jayega.
5. `intervals` vector ko `sort` function ka istemal karke sort kiya jata hai. Intervals ko unke shuruaat points ke aadhar par sort karna ensure karta hai ki overlapping intervals ek dusre ke paas ho, jisse unhe aasani se merge kiya ja sake.
6. Sabse pehla interval (sabse chota shuruaat point wala) `output` vector mein daala jata hai.
7. Ek `for` loop ka istemal kiya jata hai jisse sorted intervals mein iterate kiya jata hai, dusre interval (index 1) se shuruat karte hue.
8. Is loop ke andar, yeh check kiya jata hai ki `output` vector mein aakhri interval ka ant point (`output.back()[1]`) ya to current interval jo dekha ja raha hai ki shuruaat point (`intervals[i][0]`) se jyada hai ya barabar hai ya nahi.
- Agar overlap hota hai, to aakhri interval ke ant point ko uske current ant point aur current interval ke ant point mein se jyada wala set kiya jata hai (`output.back()[1] = max(output.back()[1], intervals[i][1]`).
— Agar overlap nahi hota hai, to iska matlab hai ki current interval aakhri interval ke saath overlap nahi karta, isliye current interval ko `output` vector mein daal diya jata hai.
9. Sabhi intervals par iterate karne ke baad, `output` vector mein merge kiye gaye intervals hote hain, aur yeh function ke result ke roop mein return kiye jate hain.
Saransh mein, yeh code ek intervals ki list leta hai, unhe unke shuruaat points ke aadhar par sort karta hai, aur phir overlapping intervals ko merge karke ek naye list mein rakhta hai. Yeh ek aam algorithm hai jo intervals ke saath kaam karne mein istemal hota hai computer science mein, aur iska istemal aksar scheduling, time-series analysis, aur aur kai applications mein hota hai.
