C++ . में दो सिटी शेड्यूलिंग

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

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

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

उदाहरण

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

#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--;
            //cout << a << " " << costs[i][0] << endl;
            ans += costs[i][0];
         } else {
            //cout << costs[i][1] << endl;
            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