C++-এ ভেগান-ফ্রেন্ডলি, দাম এবং দূরত্ব অনুযায়ী রেস্তোরাঁ ফিল্টার করা

সমস্যা বিবরণ

আমাদের কাছে রেস্তোরাঁদের একটি অ্যারে রয়েছে যেখানে প্রতিটি রেস্তোরাঁর তথ্য [id, rating, veganFriendly, price, distance] ফরম্যাটে দেওয়া থাকে। তিনটি ফিল্টার প্রয়োগ করে রেস্তোরাঁগুলো ছাঁটতে হবে:

• veganFriendly ফিল্টার: true (১) হলে শুধু ভেগান-ফ্রেন্ডলি রেস্তোরাঁই ধরে রাখা হবে; false (০) হলে সব রেস্তোরাঁ গ্রহণযোগ্য।
• maxPrice ফিল্টার: রেস্তোরাঁর দাম maxPrice-এর চেয়ে বেশি হলে বাদ দিতে হবে।
• maxDistance ফিল্টার: রেস্তোরাঁর দূরত্ব maxDistance-এর চেয়ে বেশি হলে বাদ দিতে হবে।

ফিল্টারের পর রেস্তোরাঁ আইডিগুলো রেটিংয়ের অবরোহী ক্রমে (সর্বোচ্চ থেকে নিম্নতম) সাজাতে হবে। রেটিং সমান হলে আইডি বড়টি আগে থাকবে।

উদাহরণ

রেস্তোরাঁ লিস্ট:
[[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

ফিল্টারের পর বিতর্কিত রেস্তোরাঁগুলো:

• রেস্তোরাঁ ৩: id=3, rating=8, veganFriendly=1, price=30, distance=4
• রেস্তোরাঁ ১: id=1, rating=4, veganFriendly=1, price=40, distance=10
• রেস্তোরাঁ ৫: id=5, rating=1, veganFriendly=1, price=15, distance=1

আউটপুট: [3, 1, 5] (রেটিং ৮, ৪, ১ অনুযায়ী সাজানো)

সমাধানের পদ্ধতি

1. একটি টেম্পোরারি ভেক্টর temp ঘোষণা করুন যাতে ফিল্টার পাস করা রেস্তোরাঁর [id, rating] জোড়া রাখা হবে।
2. সব রেস্তোরাঁর জন্য লুপ চালিয়ে ফিল্টার শর্তাবলী যাচাই করুন:
   • (veganFriendly == 0 || restaurant[2] == veganFriendly) && restaurant[3] <= maxPrice && restaurant[4] <= maxDistance
3. শর্ত পূরণ করলে temp-এ {id, rating} যোগ করুন।
4. temp-কে কাস্টম কমপেরেটর দিয়ে সাজান: প্রথমে rating DESC, তারপর id DESC।
5. সাজানো temp থেকে শুধু id গুলো বের করে রিটার্ন ভেক্টরে রাখুন।

C++ বাস্তবায়ন

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

class Solution {
public:
    // কাস্টম কমপেরেটর: rating বড় হলে আগে, সমান হলে id বড় হলে আগে
    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>> temp;
        
        // ফিল্টার প্রয়োগ
        for (auto& r : restaurants) {
            if ((veganFriendly == 0 || r[2] == veganFriendly) 
                && r[3] <= maxPrice 
                && r[4] <= maxDistance) {
                temp.push_back({r[0], r[1]}); // {id, rating}
            }
        }
        
        // সাজানো
        sort(temp.begin(), temp.end(), cmp);
        
        // শুধু id বের করা
        vector<int> result;
        for (auto& t : temp) result.push_back(t[0]);
        
        return result;
    }
};

// টেস্টিং용 헬퍼 ফাংশন
void printVector(const vector<int>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i + 1 < v.size()) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    vector<vector<int>> 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}
    };
    Solution ob;
    printVector(ob.filterRestaurants(restaurants, 1, 50, 10)); // আউটপুট: [3,1,5]
    return 0;
}

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n log n) — সর্টিংয়ের কারণে (n = ফিল্টার পাস করা রেস্তোরাঁর সংখ্যা)।
• স্থান জটিলতা: O(n) — টেম্পোরারি ভেক্টর সংরক্ষণের জন্য।

মূল পয়েন্টসমূহ

• ফিল্টার শর্তাবলী সঠিকভাবে বোঝা জরুরি: veganFriendly=0 মানে ভেগান শর্ত বাদ।
• সর্টিংয়ের জন্য কাস্টম কমপেরেটর লিখতে হয়।
• STL-এর sort এবং vector ব্যবহার করে কোড সংক্ষিপ্ত ও দক্ষ থাকে।