सी++ प्रोग्राम ओटीटी सेवाओं की सदस्यता लेने के लिए आवश्यक कम से कम राशि का पता लगाने के लिए

मान लीजिए, एक दूरसंचार ऑपरेटर ने "ऑल-इन-वन" नामक एक सेवा शुरू की है जो k डॉलर की निश्चित कीमत पर n OTT सामग्री प्रदाताओं तक पहुंच प्रदान करती है। अब, अगर हमें सीधे ओटीटी प्लेटफॉर्म की सदस्यता लेनी है, तो हमें प्रत्येक प्लेटफॉर्म को अलग-अलग शुल्क का भुगतान करना होगा। हमें हर महीने हर प्लेटफॉर्म पर सब्सक्रिप्शन की जरूरत नहीं है, इसलिए हमें उनकी सेवाओं का किफायती उपयोग करने का तरीका खोजना होगा। प्रारंभिक महीना जिसमें हमें प्लेटफ़ॉर्म i की सेवा की आवश्यकता होती है, सरणी start_month में दी जाती है और अंतिम महीना सरणी end_month में दिया जाता है। किसी प्लेटफ़ॉर्म की सदस्यता लेने के लिए आवश्यक मूल्य सरणी मूल्य [i] में दिया गया है। हमें अपनी आवश्यकता के अनुसार सभी प्लेटफार्मों की सदस्यता लेने के लिए कम से कम राशि का पता लगाना होगा।

इसलिए, यदि इनपुट n =3, k =10, start_month ={1, 2, 1}, end_month ={3, 3, 2}, मूल्य ={5, 7, 8} जैसा है, तो आउटपुट होगा 30

हमें 3 महीने के लिए सेवाओं की सदस्यता चाहिए।

पहले महीने में, हमें प्लेटफॉर्म 1 और 3 के लिए सब्सक्रिप्शन की आवश्यकता है। व्यक्तिगत रूप से, उनकी कुल लागत 5 + 8 =13 डॉलर है, लेकिन "ऑल-इन-वन" पैकेज के साथ इसकी कीमत केवल 10 डॉलर है। इसी तरह दूसरे महीने में हमें तीनों की जरूरत होती है जिसकी कुल कीमत 20 डॉलर होती है। लेकिन हम तीनों के लिए 10 का भुगतान करते हैं। और तीसरे महीने में, सब्सक्रिप्शन की कुल लागत 12 डॉलर हो जाती है, लेकिन हम केवल 10 का भुगतान करते हैं।

तो, कुल लागत 10 + 10 + 10 =30 है।

कदम

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

Define an array pairArray
for initialize i := 0, when i < n, update (increase i by 1), do:
   insert pair(start_month[i], price[i]) at the end of pairArray
   insert pair(end_month[i] + 1, -price[i]) at the end of pairArray
sort the array pairArray
pre := 0
c := 0
res := 0
for each element p in pairArray, do:
   day := first element of p - pre
   res := res + minimum of (k, c)
   c := c + second element of p
pre := first element of p
return res

उदाहरण

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

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

vector<vector<int>> G;
vector<int> res;

int solve(int n, int k, int start_month[], int end_month[], int price[]){
   vector<pair<int, int>> pairArray;
   for(int i = 0; i < n; i++) {
      pairArray.push_back(make_pair(start_month[i], price[i]));
      pairArray.push_back(make_pair(end_month[i] + 1, -price[i]));
   }
   sort(pairArray.begin(), pairArray.end());
   int pre = 0;
   int c = 0;
   int res = 0;
   for(auto p : pairArray) {
      int day = p.first - pre;
      res += min(k, c) * day;
      c += p.second; pre = p.first;
   }
   return res;
}
int main() {
   int n = 3, k = 10, start_month[] = {1, 2, 1}, end_month[] = {3, 3, 2}, price[] = {5, 7, 8};
   cout<< solve(n, k, start_month, end_month, price);
   return 0;
}

इनपुट

3, 10, {1, 2, 1}, {3, 3, 2}, {5, 7, 8}