Find maximum possible value of advertising

0 0 5 minutes read

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 value
int 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 Code
int 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 approach
import 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 code
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; 
     
    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 value
def 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 value
array = [[ 0, 10 ],[ 4, 110 ],[ 5, 30 ]]
 
N = 3
K = 4
M = 6
 
print(max_value(array, M, K, N))
 
# This code is contributed by shinjanpatra

C#

// C# program for above approach
 
// Include namespace system
using 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 value
function 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 value
var 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:

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 zambiatek!