C++-এ টু সিটি শিডিউলিং সমস্যা

মান लीজিয়ে 2N জন ব্যক্তি আছে। একটি কোম্পানি একটি ইন্টারভিউ আয়োজন করতে চায়। i-তম ব্যক্তিকে সিটি A-তে নিয়ে যাওয়ার খরচ costs[i][0], এবং i-তম ব্যক্তিকে সিটি B-তে নিয়ে যাওয়ার খরচ costs[i][1]। আমাদের ন্যূনতম খরচ বের করতে হবে যাতে প্রতিটি সিটিতে N জন ব্যক্তি পৌঁছায়। যেন যদি দেওয়া লিস্ট [[10, 20], [30, 200], [400, 50], [30, 20]] হয়, তবে আউটপুট হবে 110। অর্থাৎ, P1 কে সিটি A-তে 10 খরচে, দ্বিতীয় ব্যক্তিকে সিটি A-তে 30 খরচে, তৃতীয় ও চতুর্থ ব্যক্তিকে সিটি B-তে 50 এবং 20 খরচে পাঠানো হবে।

এটি সমাধান করার জন্য, আমরা নিচের ধাপগুলো অনুসরণ করব:

• n := অ্যারের সাইজ
• a := n / 2 এবং b := n / 2
• অ্যারেটি সর্ট করুন, এবং ans := 0
• i := 0 থেকে n - 1 পর্যন্ত:
  • যদি b = 0 এবং array[i, 0] <= array[i, 1] এবং a > 0, তবে
    • a ১ কমান
    • ans := ans + array[i, 0]
  • অন্যথায়
    • b ১ কমান
    • ans := ans + array[i, 1]
• ans রিটার্ন করুন

C++ উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution { public: static bool cmp(vector <int> a, vector <int> b){ return abs(a[0] - a[1]) > abs(b[0] - b[1]); } int twoCitySchedCost(vector<vector<int>>& costs) { int n = costs.size(); int a = n/2; int b = n/2; sort(costs.begin(), costs.end(), cmp); int ans = 0; for(int i = 0; i < n; i++){ if(b == 0 || (costs[i][0] <= costs[i][1] && a > 0)){ a--; ans += costs[i][0]; } else { b--; ans += costs[i][1]; } } return ans; } }; main(){ Solution ob; vector<vector<int>> c = {{10,20},{30,200},{400,50},{30,20}}; cout << ob.twoCitySchedCost(c); }

ইনপুট

[[10,20],[30,200],[400,50],[30,20]]

আউটপুট

110