C++ में दो शहर शेड्यूलिंग (Two City Scheduling)

मान लीजिए 2N व्यक्ति हैं। एक कंपनी एक साक्षात्कार आयोजित करना चाहती है। i-वें व्यक्ति को शहर A में उड़ाने की लागत costs[i][0] है, और i-वें व्यक्ति को शहर B में उड़ाने की लागत costs[i][1] है। हमें हर व्यक्ति को एक शहर में उड़ाने की न्यूनतम लागत ढूंढनी है, जैसे कि N लोग हर शहर में पहुंचें। इसलिए यदि दी गई सूची है [[10, 20], [30, 200], [400, 50], [30, 20]] तो आउटपुट 110 होगा। इसलिए हम व्यक्ति P1 को 10 लागत के साथ शहर A भेजेंगे, दूसरे व्यक्ति को 30 लागत के साथ शहर A, तीसरे और चौथे व्यक्ति को क्रमशः 50 और 20 लागत के साथ शहर B भेजेंगे।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n := सरणी का आकार
• a := n / 2 और b := n / 2
• सरणी को क्रमबद्ध करें, और ans := 0 होने दें
• i := 0 से n - 1 तक -
  • यदि b = 0 और array[i, 0] <= array[i, 1] और a > 0, तो
    • a को 1 से घटाएं
    • ans := ans + array[i, 0]
  • अन्यथा
    • b को 1 से घटाएं
    • ans := ans + array[i, 1]
• ans वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#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