Jathin

Untitled

Sep 27th, 2021
848
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for an interval.
  3.  * struct Interval {
  4.  *     int start;
  5.  *     int end;
  6.  *     Interval() : start(0), end(0) {}
  7.  *     Interval(int s, int e) : start(s), end(e) {}
  8.  * };
  9.  */
  10.  
  11. bool compareInterval(Interval i1, Interval i2)
  12. {
  13.     return (i1.start < i2.start);
  14. }
  15.  
  16. vector<Interval> Solution::merge(vector<Interval> &A) {
  17.     sort(A.begin(), A.end(), compareInterval);
  18.     stack<Interval> res;
  19.     res.push(A[0]);
  20.     for(int i = 1 ; i < A.size() ; i++){
  21.         Interval top = res.top();
  22.         if(top.end >= A[i].start){
  23.             res.pop();
  24.             Interval *temp = new Interval(top.start, max(A[i].end,top.end));
  25.             res.push(*temp);
  26.         }
  27.         else
  28.             res.push(A[i]);
  29.     }
  30.     vector<Interval>ans;
  31.     while(!res.empty()){
  32.         ans.push_back(res.top());
  33.         res.pop();
  34.     }
  35.     reverse(ans.begin(), ans.end());
  36.     return ans;
  37. }
  38.  
RAW Paste Data