C++ program to find the minimum amount required to subscribe to an OTT service

Suppose a telecom operator launches a service called "all-in-one" that provides access to n OTT content providers at a fixed price of k US dollars. access. Now, if we have to subscribe to OTT platforms directly, we have to pay separate fees to each platform. We don't need to subscribe to every platform for all months, so we have to find a way to cost-effectively use their services. We need the starting month of the service for platform i given in the array start_month and the ending month given in the array end_month. The price required to subscribe to the platform is given in the array price[i]. We have to find out the minimum amount we need to pay to subscribe to all the platforms as per our requirements.

So if the input is something like n = 3, k = 10, start_month = {1, 2, 1}, end_month = {3, 3, 2}, price = {5, 7, 8}, Then the output will be 30

We need to subscribe to the service for 3 months.

For the first month, we need to subscribe to platforms 1 and 3. Costs 5 8 = $13 each, but with the "all in one" package it costs $10 USD only. Likewise, the second month, we need all three, for a total cost of $20. But we paid $10 for those three. In the third month, the total cost of the subscription becomes $12, but we only pay $10.

Therefore, the total cost is 10 10 10 = 30.

Steps

To solve this problem we will follow the following steps-

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

Example

Let us see the following implementation for better understanding -

#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;
}

Input

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

Output

30

The above is the detailed content of C++ program to find the minimum amount required to subscribe to an OTT service. For more information, please follow other related articles on the PHP Chinese website!