GeeksForGeeks - POTD | GFG POTD Answer

class Solution 
{
    public:
    vector<int> JobScheduling(Job arr[], int n) { 
        
        set<int> slots;
        for(int i = 1; i <= n; i++)
            slots.insert(i);
        sort(arr, arr + n, [](Job& j1, Job&j2) {
           return j1.profit > j2.profit; 
        });
        
        int cnt = 0, profit = 0;
        for(int i = 0; i < n; i++) {
            Job curr = arr[i];
            auto it = slots.upper_bound(curr.dead);
            if(it == slots.begin()) continue;
            it = prev(it);
            cnt++;
            profit += curr.profit;
            slots.erase(it);
        }
        
        return {cnt, profit};
    }
};

class Solution {
  public:
    Node* rotate(Node* head, int k) 
    {
        Node * start = NULL, *end = head, *p = head;
        int i = 1;
        while(end->next != NULL)
        {
            if(k == i){start = end;}
            end = end->next;
            i++;
        }
        if(start == NULL){return head;}
        head = start->next;
        start->next = NULL;
        end->next = p;
        return head;
    }
};

class Solution {
  public:
    int mod =1e9 +7;
    int Maximize(vector<int> &arr) {
        int n =arr.size();
        sort(arr.begin(),arr.end());
        int sum =0;
        for(int i =0;i< n;i++){
            sum = (sum + 1ll*i*arr[i])%mod;
        }
        return sum;
    }
};

class Solution {
  public:
  int f(Node* root){
       if(root==NULL){
           return 0;
       }
        if(root->left==NULL && root->right==NULL){
            return root->data;
        }
        int val=f(root->left)+f(root->right);
        if(val==root->data){
            return 2*val;
        }
        return -1;
  }
    bool isSumTree(Node* root) {
        if(root==NULL){
            return true;
        }
        return f(root)==-1?false:true;
    }
};

class Solution {
  public:
    int kthElement(int k, vector<int>& arr1, vector<int>& arr2) {
        vector<int> merge;
        
        for(int i=0; i<arr1.size(); i++)
        {
            merge.push_back(arr1[i]);
        }
        
        for(int j=0; j<arr2.size(); j++)
        {
            merge.push_back(arr2[j]);
        }
        
        sort(merge.begin(), merge.end());
        
        return merge[k-1];
    }
};

class Solution {
  public:
    int isValid(string str) {
        
        vector<string>no;
        int i = 0;
        int n = str.length();
        while(i<n){
            string st;
            while(i<n && str[i]!='.'){
                st+=str[i];
                i++;
            }
            no.push_back(st);
            i++;
        }
        if(no.size()!=4){
            return false;
        }
        for(auto it:no){
            if(it.length()>3 || it.length()==0){
                return false;
            }
            int octal = 0;
            for(auto its:it){
                octal = octal*10+(its-'0');
            }
            if(octal<0 || octal>255){
                return false;
            }
            if(octal>=0 && octal<=9 && it.length()>1){
                return false;
            }
            if(octal>=10 && octal<=99 && it.length()>2){
                return false;
            }
        }
        return true;
    }
};

class Solution {
  public:
    vector <int> bottomView(Node *root) {
        
        vector<int>ans;
        if(root==NULL) return  ans;
        map<int,int>m;
        queue<pair<int,Node*>>q;
        q.push({0,root});
        while(!q.empty()){
            pair<int,Node*>temp=q.front();
            q.pop();
            int x=temp.first;
            Node* node=temp.second;
            m[x]=node->data;
            if(node->left) q.push({x-1,node->left});
            if(node->right) q.push({x+1,node->right});
        }
        for(auto i:m) ans.push_back(i.second);
        return ans;

    }
};

class Solution {
  public:
  static bool compare(pair<int,int>&a,pair<int,int>&b){
      if(a.second==b.second)
      return a.first<b.first;
      return a.second<b.second;
  }
    int maxMeetings(int n, int start[], int end[]) {
        vector<pair<int,int>>vec;
        for(int i=0;i<n;i++)
        vec.push_back({start[i],end[i]});
        sort(vec.begin(),vec.end(),compare); 
      int ans=1;
      int prev=0;
       for(int i=1;i<n;i++){
           
           if(vec[i].first>vec[prev].second){
               prev=i;
               ans++;
           }
       }
       return ans;
    }
};

class Solution {
  public:
    // Function to find if there is a celebrity in the party or not.
    int celebrity(vector<vector<int> >& mat) {
        int n=mat.size(),m=mat[0].size();
        for(int i=0;i<n;i++){
            int row=0,col=0;
            for(int j=0;j<m;j++){
                if(mat[i][j]==0) row++;
                if(mat[j][i]==1) col++;
            }
            if(row==n && col==n-1) return i;
        }
        return -1;
    }
};

class Solution {
  public:
    int editDistance(string str1, string str2) {
        // Code here
        int m = str1.size();
        int n = str2.size();
        
        // Creating a 2D Vector DP 
         vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        
        // Iterating through words
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                // If i == 0, i.e STR1 is empty, meaning it will require j number of insertions
                if(i == 0){
                    dp[i][j] = j;
                }
                
                // If j == 0; i.e STR2 is empty, meaning it will require i number of deletions
                else if(j == 0){
                    dp[i][j] = i;
                }
                
                // We got the same word, so we'll do nothing and take back the result of previous
                else if(str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                
                // Word isn't matching so we'll take minimum of insertion, removal or replacement
                else{
                    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                }
            }
        }
        
        return dp[m][n];
    }
};