Most Beautiful item for Each Query(using Binary Search)
Most Beautiful item for Each Query \n// all steps \n->>>>> \n // items - > [[2,4], [4,5], [2,1] ,[3,6] ,[1,3]]  another example i take\n      // quries-> [1,3,2
**Most Beautiful item for Each Query **\n// all steps \n->>>>> \n // items - > [[2,4], [4,5], [2,1] ,[3,6] ,[1,3]]  another example i take\n      // quries-> [1,3,2]\n\n      // fill the answer array \n      // ans = [3,6,4]\n\n\n      // sort the items array\n      // [[1,3] , [2,1] ,[2,4] ,[3,6] ,[4,5]]\n      // store prefix max in items[i][1]\n\n      // [[1,3], [2,3], [2,4], [3,6], [4,6]]\n\n      //  loop over each quries \n      // price req is quries[i]\n\n     // find a index in items array where items[i][0] > priceRequired\n\n     // the previous ind is the ans and the beauty is store over\n     // items[ind][1] \n\t \n\t \n\t \n# code -> using binary search\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        \n      \n    sort(items.begin() , items.end());\n\n    // calculate the prefix max array\n   \n    int n = items.size();\n    for(int i =0 ; i<n ; i++){\n      if(i==0) continue;\n\n      items[i][1] = max(items[i-1][1] , items[i][1] );\n    }\n\n\n   // [[1,3], [2,3], [2,4], [3,6], [4,6]]  are formed now\n\nvector<int> ans;\n\n  for(auto &priceReq : queries){\n      vector<int> dummy(2);\n\n      dummy[0] = priceReq;\n      dummy[1] = INT_MAX;\n\n      int ind = upper_bound(items.begin() , items.end() , dummy) - items.begin();\n\n      ind--;\n\n      if(ind>=0){\n        ans.push_back(items[ind][1]);\n      }else\n      {\n        ans.push_back(0);\n      } \n  }\n\n\n      \n      return ans;\n    }\n};\n\n\n
[]