Merge Intervals

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
         vector <pair<int,int>> arr;
         for(auto itr:intervals){
            arr.push_back(make_pair(itr[0],itr[1]));
         }
         sort(arr.begin(),arr.end());
         vector<vector<int>> ans;
         for(int i=0;i<arr.size();){
             vector<int> temp;
             int start=arr[i].first;
             int end=arr[i].second;
             i++;
             while(i<arr.size() && arr[i].first<=end){ end=max(end,arr[i].second);i++;}
             temp.push_back(start);
             temp.push_back(end);
             ans.push_back(temp);
         }
         return ans;
    }
};

/*
Logic:
Sort the array as per the starting value of intervals in increasing order.
Initiliaze a stack and push the first element into it and iterate the array from 1st index.
If starting value of current element is <= the ending value of stack top element then
it should be merged so merge them.
First value of top element will be for sure <= than the first element of current element
because array is sorted. so update the maximum of second values and push it in stack again.
Finally,pop all elements of stack for output.
*/

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& interval) {
       vector <pair<int,int>> arr;
        for(auto itr:interval){
            arr.push_back(make_pair(itr[0],itr[1]));
        }
        sort(arr.begin(),arr.end());
        stack<pair<int,int>> st;
        st.push(arr[0]);
        for(int i=1;i<arr.size();i++){
            pair<int,int> temp=st.top();
            if(temp.second>=arr[i].first){
                st.pop();
                temp.second=max(arr[i].second,temp.second);
                st.push(temp);
            }
            else{
                st.push(arr[i]);
            }
        }
        vector <vector <int>> res;
        while(st.size()!=0){
            pair<int,int> itr=st.top();
            st.pop();
            vector <int> temp;
            temp.push_back(itr.first);
            temp.push_back(itr.second);
            res.push_back(temp);
        }
        return res;
    }
};