Interview Question | Non- Overlapping Intervals Problem| Array | C++

Interview Question | Non- Overlapping Intervals Problem| Array | C++

bool comp(vector<int> &a,vector<int> &b) {
 return a[1]<b[1];
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int ans=-1;      
  if(intervals.size()==0) return 0;       
  sort(intervals.begin(),intervals.end(),comp);      //custom comperator is used.
  vector<int> prev= intervals[0];

  for(vector<int> i: intervals) {
   if(prev[1]>i[0]) {
    ans++;                //we dont update previous, because i[1] will be grater then prev[1]
   }else prev=i;           // we want the end point to be minimum
  }
  return ans;  
        
    }
};

English :

This C++ code defines a class Solution that contains a method eraseOverlapIntervals. This method takes a vector of intervals represented as vectors of two integers and returns the minimum number of intervals that need to be removed to make the remaining intervals non-overlapping. The intervals are sorted based on their end points using a custom comparator function comp.

Here’s a step-by-step explanation of the code:

Comparator Function (comp):

bool comp(vector<int> &a, vector<int> &b) { return a[1] < b[1]; }

This is a custom comparator function used for sorting intervals. It compares two intervals based on their second element (end point). It returns true if the end point of interval a is less than the end point of interval b, indicating that a should appear before b in the sorted order.

Class Definition (Solution):

class Solution { 
public:     int eraseOverlapIntervals(vector<vector<int>>& intervals) {         // ... (see below)     } };

Method Implementation (eraseOverlapIntervals):

int eraseOverlapIntervals(vector<vector<int>>& intervals) {     
int ans = -1;     
if (intervals.size() == 0) return 0;     
sort(intervals.begin(), intervals.end(), comp);     
vector<int> prev = intervals[0];      
  for (vector<int> i : intervals) {         
    if (prev[1] > i[0]) {             
        ans++;   } else {             
          prev = i; }     
            }     
       return ans; }

• ans is initialized to -1.
• If the input vector intervals is empty, the function returns 0 (no overlaps to remove).
• The intervals are sorted using the custom comparator comp.
• The variable prev is initialized to the first interval.
• The function then iterates through the sorted intervals.
• If the end point of the previous interval (prev[1]) is greater than the start point of the current interval (i[0]), it means there is an overlap, and ans is incremented.
• Otherwise, prev is updated to the current interval.
• The final result is the minimum number of intervals to remove (ans).

The code essentially finds the minimum number of intervals to remove in order to have a set of non-overlapping intervals. It does so by sorting the intervals based on their end points and then iterating through them to count the overlaps. The final count is the answer.

Hindi :

यह C++ कोड एक Solution नामक कक्षा को परिभाषित करता है जिसमें एक eraseOverlapIntervals नामक विधि होती है। इस विधि को दो संख्याओं के वेक्टर्स के रूप में प्रस्तुत किए गए इंटरवल्स का एक वेक्टर लेता है और बचे हुए इंटरवल्स को गैर-अवरलैपिंग बनाने के लिए हटाने के लिए आवश्यक न्यूनतम इंटरवलों की संख्या देता है। इंटरवल्स, उनके अंत बिंदुओं के आधार पर एक कस्टम कम्पेयटर फ़ंक्शन comp का उपयोग करके क्रमबद्ध किए जाते हैं।

इस कोड की चरण-दर-चरण समझ के लिए यहां एक विस्तृत विवरण है:

कम्पेयटर फ़ंक्शन (comp):

bool comp(vector<int> &a, vector<int> &b) {     return a[1] < b[1]; }

यह एक कस्टम कम्पेयटर फ़ंक्शन है जिसे इंटरवल्स को क्रमबद्ध करने के लिए उपयोग किया जाता है। यह दो इंटरवल्स को उनके दूसरे तत्व (अंत बिंदु) के आधार पर तुलना करता है। यदि इंटरवल a का अंत बिंदु इंटरवल b के अंत बिंदु से छोटा है, तो इससे यह स्पष्ट होता है कि a को b के पहले प्रकार में दिखाना चाहिए।

कक्षा परिभाषा (Solution):

class Solution { 
public:     int eraseOverlapIntervals(vector<vector<int>>& intervals) {         // ... (नीचे देखें)     } };

विधि का अमलन (eraseOverlapIntervals):

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int ans=-1;      
  if(intervals.size()==0) return 0;       
  sort(intervals.begin(),intervals.end(),comp);      //custom comperator is used.
  vector<int> prev= intervals[0];

  for(vector<int> i: intervals) {
   if(prev[1]>i[0]) {
    ans++;                //we dont update previous, because i[1] will be grater then prev[1]
   }else prev=i;           // we want the end point to be minimum
  }
  return ans;  
        
    }

• ans को -1 से आरंभ किया जाता है।
• यदि इनपुट वेक्टर intervals खाली है, तो फ़ंक्शन 0 लौटाता है (हटाने के लिए कोई ओवरलैप नहीं है)।
• इंटरवल्स comp का उपयोग करके क्रमबद्ध किए जाते हैं।
• वेरिएबल prev को पहले इंटरवल से आरंभ किया जाता है।
• फ़ंक्शन फिर क्रमबद्ध इंटरवल्स के माध्यम से यात्रा करता है।
• यदि पिछले इंटरवल का अंत बिंदु (prev[1]) वर्तमान इंटरवल के प्रारंभ बिंदु (i[0]) से अधिक है, तो इसका अर्थ है कि एक ओवरलैप है और ans को बढ़ा जाता है।
• अन्यथा, prev को वर्तमान इंटरवल से अपडेट किया जाता है।
• अंतिम परिणाम है हटाने के लिए न्यूनतम इंटरवलों की संख्या (ans)।

कोड मूल रूप से नॉन-ओवरलैपिंग इंटरवल्स प्राप्त करने के लिए हटाने की आवश्यक न्यूनतम संख्या खोजता है। यह उन्हें उनके अंत बिंदुओं के आधार पर क्रमबद्ध करके और फिर उनमें ओवरलैप्स को गिनकर करता है। अंतिम गणना उत्तर है।

Hinglish :

Is C++ code mein ek class Solution define ki gayi hai jisme ek method eraseOverlapIntervals hai. Ye method ek vector mein diye gaye intervals ko lekar aata hai jo ki do integers ke vectors ke roop mein hote hain aur bache hue intervals ko non-overlapping banane ke liye hatane ke liye kitne minimum intervals ki zarurat hai, ye bataata hai. Ye intervals apne end points ke basis par sort kiye jaate hain ek custom comparator function comp ka istemaal karke.

Yahan code ka kadam se kadam vistar se samjha jata hai:

Comparator Function (comp):

bool comp(vector<int> &a, vector<int> &b) { return a[1] < b[1]; }

Ye ek custom comparator function hai jo intervals ko sort karne ke liye istemaal hota hai. Ye do intervals ko unke doosre element (end point) ke basis par compare karta hai. Agar interval a ka end point interval b ke end point se chhota hai, toh ye true return karta hai, jisse ki sorted order mein a ko b se pehle dikhaaya jaaye.

Class Definition (Solution):

class Solution { public:     
int eraseOverlapIntervals(vector<vector<int>>& intervals) {         // ... (neeche dekhein)     } };

Method Implementation (eraseOverlapIntervals):

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int ans=-1;      
  if(intervals.size()==0) return 0;       
  sort(intervals.begin(),intervals.end(),comp);      //custom comperator is used.
  vector<int> prev= intervals[0];

  for(vector<int> i: intervals) {
   if(prev[1]>i[0]) {
    ans++;                //we dont update previous, because i[1] will be grater then prev[1]
   }else prev=i;           // we want the end point to be minimum
  }
  return ans;  
        
    }

• ans ko -1 se initialize kiya gaya hai.
• Agar input vector intervals khali hai, toh function 0 return karta hai (koi overlaps hatane ki zarurat nahi hai).
• Intervals ko comp ka istemaal karke sort kiya jata hai.
• Variable prev ko pehle interval se initialize kiya jata hai.
• Fir function sorted intervals par iterate karta hai.
• Agar pehle interval ka end point (prev[1]) current interval ke start point (i[0]) se bada hai, toh iska matlab hai ki ek overlap hai, aur ans ko increment kiya jata hai.
• Warna, prev ko current interval se update kiya jata hai.
• Antim result hai bachane ke liye minimum intervals (ans).

Ye code essentially ye nikalne ka kaam karta hai ki non-overlapping intervals hasil karne ke liye kitne minimum intervals hatane padenge. Isko ye karne ke liye intervals ko unke end points ke basis par sort karta hai aur fir unpar iterate karke overlaps ko count karta hai. Antim count hi uttar hai.