home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Filter Restaurants by Vegan-Friendly, Price and Distance ใน C++

ให้ Array restaurants แต่ละ Element = [id, rating, veganFriendly, price, distance]

Filter ด้วย 3 เงื่อนไข:

  1. veganFriendly (0/1): ถ้า 1 -> รับเฉพาะ Vegan Friendly=1, ถ้า 0 -> รับทั้งคู่
  2. maxPrice: Price ≤ maxPrice
  3. maxDistance: Distance ≤ maxDistance

คืน **Array of IDs** เรียง **Rating Descending**, Tie: **ID Descending**

ตัวอย่าง

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

Filtered:
[3,8,1,30,4] (Rating 8, Vegan, Price 30, Dist 4)
[1,4,1,40,10] (Rating 4, Vegan, Price 40, Dist 10)
[5,1,1,15,1]  (Rating 1, Vegan, Price 15, Dist 1)

Sorted by Rating Desc, ID Desc: [3, 1, 5]
Output: [3, 1, 5]

แนวทาง: Filter -> Sort -> Extract IDs

  1. Iterate Restaurants, Check Conditions -> Push {id, rating} to Temp Vector
  2. Sort Temp Vector: Comparator rating Desc, then id Desc
  3. Extract IDs to Result

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[1] != b[1]) return a[1] > b[1]; // Rating Desc
        return a[0] > b[0];                   // ID Desc
    }

    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<vector<int>> filtered;

        for (auto& r : restaurants) {
            int id = r[0], rating = r[1], vf = r[2], price = r[3], dist = r[4];
            bool veganOk = (veganFriendly == 0) || (vf == veganFriendly);
            if (veganOk && price <= maxPrice && dist <= maxDistance) {
                filtered.push_back({id, rating});
            }
        }

        sort(filtered.begin(), filtered.end(), cmp);

        vector<int> result;
        for (auto& p : filtered) result.push_back(p[0]);
        return result;
    }
};

Input / Output

Input:  [[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]] 1 50 10
Output: [3,1,5]

ความซับซ้อน (Complexity)

  • Time: O(N log N) — Filter O(N) + Sort O(N log N)
  • Space: O(N) — Filtered Vector

จุดสำคัญ

  • Vegan Filter Logic: veganFriendly==0 || r[2]==1
  • Comparator: Rating High First, ID High First (ตามโจทย์)
  • Extract เฉพาะ ID สุดท้าย

Straightforward Filtering & Sorting Problem ครับ