Given M hours of advertising limit [0, M) and N advertisements each with a start time and advertising value. Each advertisement is 1 min long. The task is to find the maximum possible advertising value achievable if the time difference between two advertisements must be at least K minutes.
Examples:
Input: Arr[][] = {{0, 10}, {4, 10}, {5, 30}}
N = 3
K = 4
M = 6
Output: 40
Either we can take advertisement starting at 0 and 4 or at 0 and 5.
Maximum Value if 40 if we take 0 and 5 pair.Input: Arr[][] = {{0, 10}, {4, 110}, {5, 30}}
N = 3
K = 4
M = 6
Output: 120
Approach:
- We will use Dynamic Programming, maintain a dp[M][2] where
- dp[i][0] represents the maximum advertising value attained if there is no advertisement starting at i-th minute,
- dp[i][1] represents the maximum advertising value attained if we select an advertisement starting at ith minute. Final answer will be maximum of dp[M-1][0] and dp[M-1][1].
- To build dp states-
- For dp[i][0], since we no advertisement starts at i-th minute, so there is no restriction of K minutes thus, dp[i][0] = max(dp[i-1][0], dp[i-1][1]) as previous minute we can have both scenario possible.
- For dp[i][1], now we have advertisement starting at i-th minute, it implies that at minutes i – 1, i – 2, …, i – (K – 1) we can’t have any advertisements. So, we must look at (i – K)-th minute. Thus, dp[i][1] = value[i] + max(dp[i-K][0], dp[i-K][1]), as at minute i – K we can again have both the scenarios.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long int// Function to find maximum// possible advertising valueint max_value(int array[][2], int M, int K, int N){ // To store advertising // value at i-th minute int time[M] = { 0 }; for (int i = 0; i < N; i++) { time[array[i][0]] = array[i][1]; } int dp[M][2]; // Base Case dp[0][0] = 0; dp[0][1] = time[0]; for (int i = 1; i < M; i++) { // If no advertisement is // taken on ith minute dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); // If advertisement is taken // on i-th minute dp[i][1] = time[i]; if (i - K >= 0) { dp[i][1] += max(dp[i - K][0], dp[i - K][1]); } } return max(dp[M - 1][0], dp[M - 1][1]);}// Driver's Codeint main(){ // array[][0] start time // array[][1] advertising value int array[][2] = { { 0, 10 }, { 4, 110 }, { 5, 30 } }; int N = 3; int K = 4; int M = 6; cout << max_value(array, M, K, N);} |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG{ // Function to find maximum // possible advertising value static int max_value(int array[][], int M, int K, int N) { // To store advertising // value at i-th minute int[] time = new int[M]; for(int i = 0; i < N; i++) { time[array[i][0]] = array[i][1]; } int[][] dp = new int[M][2]; // Base Case dp[0][0] = 0; dp[0][1] = time[0]; for(int i = 1; i < M; i++) { // If no advertisement is // taken on ith minute dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]); // If advertisement is taken // on i-th minute dp[i][1] = time[i]; if (i - K >= 0) { dp[i][1] += Math.max(dp[i - K][0], dp[i - K][1]); } } return Math.max(dp[M - 1][0], dp[M - 1][1]); } // Driver codepublic static void main(String[] args){ // array[][0] start time // array[][1] advertising value int array[][] = { { 0, 10 }, { 4, 110 }, { 5, 30 } }; int N = 3; int K = 4; int M = 6; System.out.println(max_value(array, M, K, N));}}// This code is contributed by offbeat |
Python3
# Python program for the above approach# Function to find maximum# possible advertising valuedef max_value(array, M,K,N): # To store advertising # value at i-th minute time = [ 0 for i in range(M)] for i in range(N): time[array[i][0]] = array[i][1] dp = [[0 for i in range(2)]for j in range(M)] # Base Case dp[0][0] = 0 dp[0][1] = time[0] for i in range(1,M): # If no advertisement is # taken on ith minute dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) # If advertisement is taken # on i-th minute dp[i][1] = time[i] if (i - K >= 0): dp[i][1] += max(dp[i - K][0], dp[i - K][1]) return max(dp[M - 1][0], dp[M - 1][1])# Driver's Code# array[][0] start time# array[][1] advertising valuearray = [[ 0, 10 ],[ 4, 110 ],[ 5, 30 ]]N = 3K = 4M = 6print(max_value(array, M, K, N))# This code is contributed by shinjanpatra |
C#
// C# program for above approach// Include namespace systemusing System;using System.Collections.Generic;using System.Linq;using System.Collections;public class GFG{// Function to find maximum // possible advertising value static int max_value(int[,] array, int M, int K, int N) { // To store advertising // value at i-th minute int[] time = new int[M]; for(int i = 0; i < N; i++) { time[array[i, 0]] = array[i, 1]; } int[,] dp = new int[M, 2]; // Base Case dp[0, 0] = 0; dp[0, 1] = time[0]; for(int i = 1; i < M; i++) { // If no advertisement is // taken on ith minute dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1]); // If advertisement is taken // on i-th minute dp[i, 1] = time[i]; if (i - K >= 0) { dp[i, 1] += Math.Max(dp[i - K, 0], dp[i - K, 1]); } } return Math.Max(dp[M - 1, 0], dp[M - 1, 1]); } public static void Main(String[] args) { // array[][0] start time // array[][1] advertising value int[,] array = { { 0, 10 }, { 4, 110 }, { 5, 30 } }; int N = 3; int K = 4; int M = 6; Console.WriteLine(max_value(array, M, K, N)); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript program for the above approach// Function to find maximum// possible advertising valuefunction max_value(array, M, K, N){ // To store advertising // value at i-th minute var time = Array(M).fill(0); for (var i = 0; i < N; i++) { time[array[i][0]] = array[i][1]; } var dp = Array.from(Array(M), ()=> Array(2)); // Base Case dp[0][0] = 0; dp[0][1] = time[0]; for (var i = 1; i < M; i++) { // If no advertisement is // taken on ith minute dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]); // If advertisement is taken // on i-th minute dp[i][1] = time[i]; if (i - K >= 0) { dp[i][1] += Math.max(dp[i - K][0], dp[i - K][1]); } } return Math.max(dp[M - 1][0], dp[M - 1][1]);}// Driver's Code// array[][0] start time// array[][1] advertising valuevar array = [ [ 0, 10], [ 4, 110 ], [ 5, 30 ]];var N = 3;var K = 4;var M = 6;document.write( max_value(array, M, K, N));</script> |
Output:
120
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
