{"id":6146,"date":"2020-01-26T21:02:04","date_gmt":"2020-01-27T05:02:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6146"},"modified":"2020-01-26T21:02:56","modified_gmt":"2020-01-27T05:02:56","slug":"leetcode-1333-filter-restaurants-by-vegan-friendly-price-and-distance","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1333-filter-restaurants-by-vegan-friendly-price-and-distance\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance"},"content":{"rendered":"\n

Given the array restaurants<\/code> where  restaurants[i] = [idi<\/sub>, ratingi<\/sub>, veganFriendlyi<\/sub>, pricei<\/sub>, distancei<\/sub>]<\/code>. You have to filter the restaurants using three filters.<\/p>\n\n\n\n

The veganFriendly<\/code> filter will be either true<\/em> (meaning you should only include restaurants with veganFriendlyi<\/sub><\/code> set to true) or false<\/em> (meaning you can include any restaurant). In addition, you have the filters maxPrice<\/code> and maxDistance<\/code> which are the maximum value for price and distance of restaurants you should consider respectively.<\/p>\n\n\n\n

Return the array of restaurant IDs<\/strong><\/em> after filtering, ordered by rating<\/strong> from highest to lowest. For restaurants with the same rating, order them by id<\/strong><\/em> from highest to lowest. For simplicity veganFriendlyi<\/sub><\/code> and veganFriendly<\/code> take value 1<\/em> when it is true<\/em>, and 0<\/em> when it is false<\/em>.<\/p>\n\n\n\n

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

Input:<\/strong> restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10\nOutput:<\/strong> [3,1,5] \nExplanation: \n<\/strong>The restaurants are:\nRestaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]\nRestaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]\nRestaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]\nRestaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]\nRestaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] \nAfter filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest). \n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10\nOutput:<\/strong> [4,3,2,1,5]\nExplanation:<\/strong> The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3\nOutput:<\/strong> [4,5]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= restaurants.length <= 10^4<\/code><\/li>
  • restaurants[i].length == 5<\/code><\/li>
  • 1 <= idi<\/sub>, ratingi<\/sub>, pricei<\/sub>, distancei <\/sub><= 10^5<\/code><\/li>
  • 1 <= maxPrice, maxDistance <= 10^5<\/code><\/li>
  • veganFriendlyi<\/sub><\/code> and veganFriendly<\/code> are 0 or 1.<\/li>
  • All idi<\/sub><\/code> are distinct.<\/li><\/ul>\n\n\n\n
    Solution<\/strong><\/h2>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector filterRestaurants(vector>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {\n    vector> rs; \/\/ \n    for (auto& r : restaurants)\n      if ((!veganFriendly || veganFriendly && r[2]) && r[3] <= maxPrice && r[4] <= maxDistance)\n        rs.emplace_back(r[1], r[0]);\n    \n    sort(rbegin(rs), rend(rs));    \n    vector ans;\n    for (const auto& r : rs) ans.push_back(r.second);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Given the array restaurants where  restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]. You have to filter the restaurants using three filters. The veganFriendly filter will be either true (meaning you should…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[537,177,377,179,15],"class_list":["post-6146","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-filter","tag-medium","tag-onlogn","tag-simulation","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6146","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=6146"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6146\/revisions"}],"predecessor-version":[{"id":6148,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6146\/revisions\/6148"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}