मान लीजिए एक टेलीकॉम ऑपरेटर ने "ऑल-इन-वन" सेवा शुरू की है जो n OTT कंटेंट प्रदाताओं तक पहुँच प्रदान करती है जिसकी निश्चित कीमत k डॉलर है। अब यदि हमें सीधे OTT प्लेटफॉर्म की सदस्यता लेनी हो, तो हमें प्रत्येक प्लेटफॉर्म को व्यक्तिगत शुल्क देना होगा। हमें हर महीने सभी प्लेटफॉर्म की आवश्यकता नहीं होती, इसलिए हमें उनकी सेवाओं का लागत-प्रभावी तरीके से उपयोग करना होगा। प्लेटफॉर्म i की आवश्यकता का प्रारंभिक महीना 'start_month' सरणी में और अंतिम महीना 'end_month' सरणी में दिया गया है। प्लेटफॉर्म की सदस्यता की कीमत 'price[i]' सरणी में दी गई है। हमें अपनी आवश्यकता के अनुसार सभी प्लेटफॉर्म की सदस्यता के लिए भुगतान की जाने वाली न्यूनतम धनराशि ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है n = 3, k = 10, start_month = {1, 2, 1}, end_month = {3, 3, 2}, price = {5, 7, 8}, तो आउटपुट 30 होगा।
हमें 3 महीने तक सेवाओं की आवश्यकता है।
पहले महीने में, हमें प्लेटफॉर्म 1 और 3 की आवश्यकता है। व्यक्तिगत रूप से उनकी लागत 5 + 8 = 13 डॉलर है, लेकिन "ऑल-इन-वन" पैकेज के साथ केवल 10 डॉलर। इसी तरह दूसरे महीने में तीनों की आवश्यकता है जिसकी कुल लागत 20 डॉलर है लेकिन हम 10 डॉलर देते हैं। तीसरे महीने में कुल लागत 12 डॉलर है लेकिन हम केवल 10 देते हैं।
कुल लागत 10 + 10 + 10 = 30।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक सरणी pairArray परिभाषित करें
i := 0 से n-1 तक:
युग्म (start_month[i], price[i]) को pairArray के अंत में डालें
युग्म (end_month[i] + 1, -price[i]) को pairArray के अंत में डालें
pairArray को सॉर्ट करें
pre := 0
c := 0
res := 0
pairArray में प्रत्येक तत्व p के लिए:
day := p का पहला मान - pre
res := res + min(k, c) * day
c := c + p का दूसरा मान
pre := p का पहला मान
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}
आउटपुट
30