{"id":8699,"date":"2021-11-14T14:27:39","date_gmt":"2021-11-14T22:27:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8699"},"modified":"2021-11-14T14:29:17","modified_gmt":"2021-11-14T22:29:17","slug":"leetcode-2070-most-beautiful-item-for-each-query","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-2070-most-beautiful-item-for-each-query\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2070. Most Beautiful Item for Each Query"},"content":{"rendered":"\n

You are given a 2D integer array items<\/code> where items[i] = [pricei<\/sub>, beautyi<\/sub>]<\/code> denotes the price<\/strong> and beauty<\/strong> of an item respectively.<\/p>\n\n\n\n

You are also given a 0-indexed<\/strong> integer array queries<\/code>. For each queries[j]<\/code>, you want to determine the maximum beauty<\/strong> of an item whose price<\/strong> is less than or equal<\/strong> to queries[j]<\/code>. If no such item exists, then the answer to this query is 0<\/code>.<\/p>\n\n\n\n

Return an array <\/em>answer<\/code> of the same length as <\/em>queries<\/code> where <\/em>answer[j]<\/code> is the answer to the <\/em>jth<\/sup><\/code> query<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]\nOutput:<\/strong> [2,4,5,5,6,6]\nExplanation:<\/strong>\n- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.\n- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. \n  The maximum beauty among them is 4.\n- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].\n  The maximum beauty among them is 5.\n- For queries[4]=5 and queries[5]=6, all items can be considered.\n  Hence, the answer for them is the maximum beauty of all items, i.e., 6.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]\nOutput:<\/strong> [4]\nExplanation:<\/strong> \nThe price of every item is equal to 1, so we choose the item with the maximum beauty 4. \nNote that multiple items can have the same price and\/or beauty.  \n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> items = [[10,1000]], queries = [5]\nOutput:<\/strong> [0]\nExplanation:<\/strong>\nNo item has a price less than or equal to 5, so no item can be chosen.\nHence, the answer to the query is 0.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= items.length, queries.length <= 105<\/sup><\/code><\/li>
  • items[i].length == 2<\/code><\/li>
  • 1 <= pricei<\/sub>, beautyi<\/sub>, queries[j] <= 109<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Prefix Max + Binary Search<\/strong><\/h2>\n\n\n\n
    Sort items by price. For each price, use a treemap to store the max beauty of an item whose prices is <= p. Then use binary search to find the max beauty whose price is <= p.<\/p>\n\n\n\n
    Time complexity: Pre-processing O(nlogn) + query: O(qlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector maximumBeauty(vector>& items, vector& queries) {\n    sort(begin(items), end(items));\n    map m;\n    int best = 0;\n    for (const auto& item : items) {\n      best = max(best, item[1]);\n      m[item[0]] = best;\n    }\n    vector ans;\n    for (const int q: queries) {\n      auto it = m.upper_bound(q);\n      if (it == begin(m))\n        ans.push_back(0);\n      else\n        ans.push_back(prev(it)->second);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively. You are also given a 0-indexed integer array queries. For each queries[j], you want to…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177,726,699],"class_list":["post-8699","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","tag-queries","tag-treemap","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8699","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8699"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8699\/revisions"}],"predecessor-version":[{"id":8701,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8699\/revisions\/8701"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8699"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8699"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8699"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}