Given a sorted array arr[] consisting of N positive integers such that arr[i] represent the days in which a worker will work and an array cost[] of size 3 representing the salary paid to the workers for 1 day, 7 days and 30 days respectively, the task is to find the minimum cost required to have a worker for all the given days in arr[].
Examples:
Input: arr[] = [2, 4, 6, 7, 8, 10, 17], cost[] = [3, 8, 20]
Output: 14
Explanation:
Below is one of the possible ways of hiring workers with minimum cost:
- On day 2, call a worker for 1 day which costs cost[0] = 3.
- On day 4, call a worker for 7-day which costs cost[1] = 8, which covers day 4, 5, …, 10.
- On day 17, call worker for 1-day which costs cost[0] = 3, which covers day 17.
Therefore, the total cost is 3 + 8 + 3 = 14, which is minimum among all possible combinations of hiring workers.
Input: arr[]= [1, 2, 3, 4, 6, 7, 8, 9, 11, 15, 20, 29], cost = [3, 8, 10]
Output: 10
Approach: The given above problem can be solved using Dynamic Programming because it has Optimal Substructure and Overlapping Subproblems. Follow the steps below to solve the problem:
- Initialize an array, say dp[] where dp[i] stores the minimum cost required to have a worker on the days [i, arr[N – 1]].
- Initialize the value of dp[arr[N – 1]] as the minimum of {cost[0], cost[1], cost[2]}.
- Initialize a variable, say ptr that points at the current element of the array arr[].
- Iterate over the range [arr[N – 1] – 1, 0] using the variable i and perform the following steps:
- If the value of ptr >= 0 and arr[ptr] == i then,
- Initialize a variable, say val1 and modify the value as dp[i + 1] + cost[0].
- Initialize a variable, say val2 and modify the value as dp[i + 7] + cost[1].
- Initialize a variable say val3 and modify the value as dp[i + 30] + cost[2].
- Now, update the value of dp[i] as the minimum of {val1, val2, val3}.
- Decrease the value of ptr by 1.
- Otherwise, update the value of dp[i] as dp[i + 1].
- If the value of ptr >= 0 and arr[ptr] == i then,
- After completing the above steps, print the value of dp[1] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost// to hire the workers for the given// days in the array days[]int MinCost(int days[], int cost[], int N){ int size = days[N - 1] + 1; // Initialize the array dp int dp[size]; // Minimum Cost for Nth day dp[size - 1] = min(cost[0], min(cost[1], cost[2])); // Pointer of the array arr[] int ptr = N - 2; // Traverse from right to left for (int i = size - 2; i > 0; i--) { if (ptr >= 0 && days[ptr] == i) { // If worker is hired for 1 day int val1 = dp[i + 1] + cost[0]; // If worker is hired for 7 days int val2 = cost[1] + ((i + 7 >= size) ? 0 : dp[i + 7]); // If worker is hired for 30 days int val3 = cost[2] + ((i + 30 >= size) ? 0 : dp[i + 30]); // Update the value of dp[i] as // minimum of 3 options dp[i] = min(val1, min(val2, val3)); ptr--; } // If the day is not at the // array arr[] else { dp[i] = dp[i + 1]; } } // Return the answer return dp[1];}// Driver Codeint main(){ int arr[] = { 2, 4, 6, 7, 8, 10, 17 }; int cost[] = { 3, 8, 20 }; int N = sizeof(arr) / sizeof(arr[0]); cout << MinCost(arr, cost, N); return 0;} |
Java
// Java program for the above approachpublic class GFG{// Function to find the minimum cost// to hire the workers for the given// days in the array days[]static int MinCost(int days[], int cost[], int N){ int size = days[N - 1] + 1; // Initialize the array dp int []dp = new int[size]; // Minimum Cost for Nth day dp[size - 1] = Math.min(cost[0], Math.min(cost[1], cost[2])); // Pointer of the array arr[] int ptr = N - 2; // Traverse from right to left for (int i = size - 2; i > 0; i--) { if (ptr >= 0 && days[ptr] == i) { // If worker is hired for 1 day int val1 = dp[i + 1] + cost[0]; // If worker is hired for 7 days int val2 = cost[1] + ((i + 7 >= size) ? 0 : dp[i + 7]); // If worker is hired for 30 days int val3 = cost[2] + ((i + 30 >= size) ? 0 : dp[i + 30]); // Update the value of dp[i] as // minimum of 3 options dp[i] = Math.min(val1, Math.min(val2, val3)); ptr--; } // If the day is not at the // array arr[] else { dp[i] = dp[i + 1]; } } // Return the answer return dp[1];}// Driver Codepublic static void main(String args[]) { int arr[] = { 2, 4, 6, 7, 8, 10, 17 }; int cost[] = { 3, 8, 20 }; int N = arr.length; System.out.println(MinCost(arr, cost, N));}}// This code is contributed by SoumikMondal |
Python3
# Python Program for the above approach# Function to find the minimum cost# to hire the workers for the given# days in the array days[]def MinCost(days, cost, N): size = days[N - 1] + 1 # Initialize the array dp dp = [0 for i in range(size)] # Minimum Cost for Nth day dp[size - 1] = min(cost[0], min(cost[1], cost[2])) # Pointer of the array arr[] ptr = N - 2 # Traverse from right to left for i in range(size - 2, 0, -1): if (ptr >= 0 and days[ptr] == i): # If worker is hired for 1 day val1 = dp[i + 1] + cost[0] # If worker is hired for 7 days val2 = cost[1] + ( 0 if (i + 7 >= size) else dp[i + 7]) # If worker is hired for 30 days val3 = cost[2] + ( 0 if (i + 30 >= size) else dp[i + 30]) # Update the value of dp[i] as # minimum of 3 options dp[i] = min(val1, min(val2, val3)) ptr -= 1; # If the day is not at the # array arr[] else: dp[i] = dp[i + 1] # Return the answer return dp[1]# Driver Codearr = [2, 4, 6, 7, 8, 10, 17]cost = [3, 8, 20]N = len(arr)print(MinCost(arr, cost, N))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{// Function to find the minimum cost// to hire the workers for the given// days in the array days[]static int MinCost(int[] days, int[] cost, int N){ int size = days[N - 1] + 1; // Initialize the array dp int[] dp = new int[size]; // Minimum Cost for Nth day dp[size - 1] = Math.Min( cost[0], Math.Min(cost[1], cost[2])); // Pointer of the array arr[] int ptr = N - 2; // Traverse from right to left for(int i = size - 2; i > 0; i--) { if (ptr >= 0 && days[ptr] == i) { // If worker is hired for 1 day int val1 = dp[i + 1] + cost[0]; // If worker is hired for 7 days int val2 = cost[1] + ((i + 7 >= size) ? 0 : dp[i + 7]); // If worker is hired for 30 days int val3 = cost[2] + ((i + 30 >= size) ? 0 : dp[i + 30]); // Update the value of dp[i] as // minimum of 3 options dp[i] = Math.Min(val1, Math.Min(val2, val3)); ptr--; } // If the day is not at the // array arr[] else { dp[i] = dp[i + 1]; } } // Return the answer return dp[1];}// Driver Codepublic static void Main(){ int[] arr = { 2, 4, 6, 7, 8, 10, 17 }; int[] cost = { 3, 8, 20 }; int N = arr.Length; Console.WriteLine(MinCost(arr, cost, N));}}// This code is contributed by subhammahato348 |
Javascript
<script> // JavaScript Program for the above approach // Function to find the minimum cost // to hire the workers for the given // days in the array days[] function MinCost(days, cost, N) { let size = days[N - 1] + 1; // Initialize the array dp let dp = new Array(size); // Minimum Cost for Nth day dp[size - 1] = Math.min(cost[0], Math.min(cost[1], cost[2])); // Pointer of the array arr[] let ptr = N - 2; // Traverse from right to left for (let i = size - 2; i > 0; i--) { if (ptr >= 0 && days[ptr] == i) { // If worker is hired for 1 day let val1 = dp[i + 1] + cost[0]; // If worker is hired for 7 days let val2 = cost[1] + ((i + 7 >= size) ? 0 : dp[i + 7]); // If worker is hired for 30 days let val3 = cost[2] + ((i + 30 >= size) ? 0 : dp[i + 30]); // Update the value of dp[i] as // minimum of 3 options dp[i] = Math.min(val1, Math.min(val2, val3)); ptr--; } // If the day is not at the // array arr[] else { dp[i] = dp[i + 1]; } } // Return the answer return dp[1]; } // Driver Code let arr = [2, 4, 6, 7, 8, 10, 17]; let cost = [3, 8, 20]; let N = arr.length; document.write(MinCost(arr, cost, N)); // This code is contributed by Potta Lokesh </script> |
Output
14
Time Complexity: O(M), where M is the maximum element of the array.
Auxiliary Space: O(M)
Recursive Approach:
We have three options:
- Select either First Pass, Second Pass, or Last Pass.
- If a day falls within the validity period of a previously selected pass, we can travel without incurring any expenses.
- The base rule is that if we finish our journey, we won’t have to pay anything.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost// to hire the workers for the given// days in the array days[]int solve(int days[], int costs[], int i, int validity, int N){ if (i >= N) return 0; if (days[i] <= validity) return solve(days, costs, i + 1, validity, N); else { int ch1 = costs[0] + solve(days, costs, i + 1, days[i], N); int ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N); int ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N); return min(ch1, min(ch2, ch3)); }}int MinCost(int days[], int cost[], int N){ return solve(days, cost, 0, 0, N);}// Driver Codeint main(){ int arr[] = { 2, 4, 6, 7, 8, 10, 17 }; int cost[] = { 3, 8, 20 }; int N = sizeof(arr) / sizeof(arr[0]); cout << MinCost(arr, cost, N); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;public class Main { // Function to find the minimum cost // to hire the workers for the given // days in the array days[] public static int solve(int[] days, int[] costs, int i, int validity, int N) { if (i >= N) return 0; if (days[i] <= validity) return solve(days, costs, i + 1, validity, N); else { int ch1 = costs[0] + solve(days, costs, i + 1, days[i], N); int ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N); int ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N); return Math.min(ch1, Math.min(ch2, ch3)); } } public static int MinCost(int[] days, int[] cost, int N) { return solve(days, cost, 0, 0, N); } // Driver Code public static void main(String[] args) { int[] arr = { 2, 4, 6, 7, 8, 10, 17 }; int[] cost = { 3, 8, 20 }; int N = arr.length; System.out.println(MinCost(arr, cost, N)); }} |
Python3
# Python3 program for the above approach# Function to find the minimum cost# to hire the workers for the given# days in the array days[]def solve(days, costs, i, validity, N): if i >= N: return 0 if days[i] <= validity: return solve(days, costs, i + 1, validity, N) else: ch1 = costs[0] + solve(days, costs, i + 1, days[i], N) ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N) ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N) return min(ch1, min(ch2, ch3))def MinCost(days, cost, N): return solve(days, cost, 0, 0, N)# Driver Codeif __name__ == '__main__': arr = [2, 4, 6, 7, 8, 10, 17] cost = [3, 8, 20] N = len(arr) print(MinCost(arr, cost, N)) |
C#
using System;public class GFG{ // Function to find the minimum cost // to hire the workers for the given // days in the array days[] public static int Solve(int[] days, int[] costs, int i, int validity, int N) { if (i >= N) return 0; if (days[i] <= validity) return Solve(days, costs, i + 1, validity, N); else { int ch1 = costs[0] + Solve(days, costs, i + 1, days[i], N); int ch2 = costs[1] + Solve(days, costs, i + 1, days[i] + 6, N); int ch3 = costs[2] + Solve(days, costs, i + 1, days[i] + 29, N); return Math.Min(ch1, Math.Min(ch2, ch3)); } } public static int MinCost(int[] days, int[] cost, int N) { return Solve(days, cost, 0, 0, N); } // Driver Code public static void Main() { int[] arr = { 2, 4, 6, 7, 8, 10, 17 }; int[] cost = { 3, 8, 20 }; int N = arr.Length; Console.WriteLine(MinCost(arr, cost, N)); }} |
Javascript
// Javascript program for the above approach// Function to find the minimum cost// to hire the workers for the given// days in the array days[]function solve(days, costs, i, validity, N){ if (i >= N) return 0; if (days[i] <= validity) return solve(days, costs, i + 1, validity, N); else { let ch1 = costs[0] + solve(days, costs, i + 1, days[i], N); let ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N); let ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N); return Math.min(ch1, Math.min(ch2, ch3)); }}function MinCost(days, cost, N){ return solve(days, cost, 0, 0, N);}// Driver Codelet arr = [2, 4, 6, 7, 8, 10, 17];let cost = [3, 8, 20];let N = arr.length;console.log(MinCost(arr, cost, N));// The code is contributed by Nidhi goel. |
Output
14
- Time Complexity: O(3N), where N = size of array
- Auxiliary Space: O(N)
Dp Memoization (DP Approach):
Cache the recursive result and don’t recompute the repeated subproblems
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost// to hire the workers for the given// days in the array days[]int solve(int days[], int costs[], int i, int validity, int N, vector<vector<int> >& dp){ if (i >= N) return 0; if (dp[i][validity] != -1) return dp[i][validity]; if (days[i] <= validity) return dp[i][validity] = solve(days, costs, i + 1, validity, N, dp); else { int ch1 = costs[0] + solve(days, costs, i + 1, days[i], N, dp); int ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N, dp); int ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N, dp); return dp[i][validity] = min(ch1, min(ch2, ch3)); }}int MinCost(int days[], int cost[], int n){ int max_validity = days[n - 1] + 30; vector<vector<int> > dp(n, vector<int>(max_validity, -1)); return solve(days, cost, 0, 0, n, dp);}// Driver Codeint main(){ int arr[] = { 2, 4, 6, 7, 8, 10, 17 }; int cost[] = { 3, 8, 20 }; int N = sizeof(arr) / sizeof(arr[0]); cout << MinCost(arr, cost, N); return 0;} |
Java
//Java code for above implementationimport java.util.*;class GFG { // Driver code public static void main(String[] args) { int[] arr = { 2, 4, 6, 7, 8, 10, 17 }; int[] cost = { 3, 8, 20 }; int N = arr.length; System.out.println(MinCost(arr, cost, N)); } public static int MinCost(int[] days, int[] cost, int n) { int max_validity = days[n - 1] + 30; int[][] dp = new int[n][max_validity]; for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1); return solve(days, cost, 0, 0, n, dp); } // Function to find the minimum cost // to hire the workers for the given // days in the array days[] public static int solve(int[] days, int[] costs, int i, int validity, int N, int[][] dp) { if (i >= N) return 0; if (dp[i][validity] != -1) return dp[i][validity]; if (days[i] <= validity) return dp[i][validity] = solve( days, costs, i + 1, validity, N, dp); else { int ch1 = costs[0] + solve(days, costs, i + 1, days[i], N, dp); int ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N, dp); int ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N, dp); return dp[i][validity] = Math.min(ch1, Math.min(ch2, ch3)); } }} |
Python3
# Function to find the minimum cost# to hire the workers for the given# days in the array days[]def solve(days, costs, i, validity, N, dp): if i >= N: return 0 if dp[i][validity] != -1: return dp[i][validity] if days[i] <= validity: return solve(days, costs, i + 1, validity, N, dp) else: ch1 = costs[0] + solve(days, costs, i + 1, days[i], N, dp) ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N, dp) ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N, dp) dp[i][validity] = min(ch1, min(ch2, ch3)) return dp[i][validity]def MinCost(days, cost, n): max_validity = days[n - 1] + 30 dp = [[-1 for j in range(max_validity)] for i in range(n)] return solve(days, cost, 0, 0, n, dp)# Driver Codearr = [2, 4, 6, 7, 8, 10, 17]cost = [3, 8, 20]N = len(arr)print(MinCost(arr, cost, N)) |
C#
using System;using System.Collections.Generic;class GFG { // Function to find the minimum cost // to hire the workers for the given // days in the array days[] static int Solve(int[] days, int[] costs, int i, int validity, int N, List<List<int> > dp) { if (i >= N) return 0; if (dp[i][validity] != -1) return dp[i][validity]; if (days[i] <= validity) return dp[i][validity] = Solve( days, costs, i + 1, validity, N, dp); else { int ch1 = costs[0] + Solve(days, costs, i + 1, days[i], N, dp); int ch2 = costs[1] + Solve(days, costs, i + 1, days[i] + 6, N, dp); int ch3 = costs[2] + Solve(days, costs, i + 1, days[i] + 29, N, dp); return dp[i][validity] = Math.Min(ch1, Math.Min(ch2, ch3)); } } static int MinCost(int[] days, int[] cost, int n) { int max_validity = days[n - 1] + 30; List<List<int> > dp = new List<List<int> >(); for (int i = 0; i < n; i++) { List<int> temp = new List<int>(); for (int j = 0; j < max_validity; j++) temp.Add(-1); dp.Add(temp); } return Solve(days, cost, 0, 0, n, dp); } // Driver Code static void Main() { int[] arr = { 2, 4, 6, 7, 8, 10, 17 }; int[] cost = { 3, 8, 20 }; int N = arr.Length; Console.WriteLine(MinCost(arr, cost, N)); }} |
Javascript
// Function to find the minimum cost// to hire the workers for the given// days in the array days[]function solve(days, costs, i, validity, N, dp) { if (i >= N) { return 0; } if (dp[i][validity] != -1) { return dp[i][validity]; } if (days[i] <= validity) { return solve(days, costs, i + 1, validity, N, dp); } else { let ch1 = costs[0] + solve(days, costs, i + 1, days[i], N, dp); let ch2 = costs[1] + solve(days, costs, i + 1, days[i] + 6, N, dp); let ch3 = costs[2] + solve(days, costs, i + 1, days[i] + 29, N, dp); dp[i][validity] = Math.min(ch1, Math.min(ch2, ch3)); return dp[i][validity]; }}function MinCost(days, cost, n) { let max_validity = days[n - 1] + 30; let dp = new Array(n); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(max_validity).fill(-1); } return solve(days, cost, 0, 0, n, dp);}// Driver Codelet arr = [2, 4, 6, 7, 8, 10, 17];let cost = [3, 8, 20];let N = arr.length;console.log(MinCost(arr, cost, N)); |
Output
14
Time Complexity: O(N), where N = size of array
Auxiliary Space: O(N)
Efficient Approach Using Queues:
Intuition:
Use two queues to keep the indices of the days that are no earlier than the ith day by 7 days and 30 days, respectively.idea behind using queue from no of expired days which will be of no use . So i’ll be removing those using 2 Queues
“1 for days in month and 2nd one for days in week”
Because our final ans(cost obtained) will be min(cost(days), cost(week), cost(month).
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost// to hire the workers for the given// days in the array days[]int MinCost(vector<int>& days, vector<int>& costs){ queue<pair<int, int> > qmonth; queue<pair<int, int> > qweek; // Don't initialize with INT_MAX otherwise ans will go // in -ve range(i.e wrong answer will be obtained) int ans = 0; // loop over days array for (int day : days) { /* Below is intution behind using queue in this * question */ // Step1: remove expired days from both queues while (!qmonth.empty() && qmonth.front().first + 30 <= day) { qmonth.pop(); } while (!qweek.empty() && qweek.front().first + 7 <= day) { qweek.pop(); } // Step2: add current day's cost qmonth.push(make_pair(day, ans + costs[2])); qweek.push(make_pair(day, ans + costs[1])); // Step3: Update ans ans = min(ans + costs[0], min(qmonth.front().second, qweek.front().second)); } return ans;}// Driver Codeint main(){ vector<int> arr{ 2, 4, 6, 7, 8, 10, 15 }; vector<int> cost{ 3, 108, 20 }; cout << MinCost(arr, cost); return 0;} |
Java
import java.util.LinkedList;import java.util.Queue;import java.util.Vector;public class Main { // Function to find the minimum cost to hire the workers static int minCost(Vector<Integer> days, Vector<Integer> costs) { Queue<Pair<Integer, Integer> > qmonth = new LinkedList<>(); Queue<Pair<Integer, Integer> > qweek = new LinkedList<>(); // Don't initialize with Integer.MAX_VALUE otherwise // the 'ans' will go in the negative range (i.e. // wrong answer will be obtained) int ans = 0; // Loop over the days array for (int day : days) { /* Below is the intuition behind using queues in * this question */ // Step 1: Remove expired days from both queues while (!qmonth.isEmpty() && qmonth.peek().getKey() + 30 <= day) { qmonth.poll(); } while (!qweek.isEmpty() && qweek.peek().getKey() + 7 <= day) { qweek.poll(); } // Step 2: Add the current day's cost qmonth.add(new Pair<>(day, ans + costs.get(2))); qweek.add(new Pair<>(day, ans + costs.get(1))); // Step 3: Update ans ans = Math.min( ans + costs.get(0), Math.min(qmonth.peek().getValue(), qweek.peek().getValue())); } return ans; } // Pair class to store pairs of integers static class Pair<K, V> { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } } // Driver Code public static void main(String[] args) { Vector<Integer> days = new Vector<>(); days.add(2); days.add(4); days.add(6); days.add(7); days.add(8); days.add(10); days.add(15); Vector<Integer> costs = new Vector<>(); costs.add(3); costs.add(108); costs.add(20); System.out.println("Minimum cost to hire workers: " + minCost(days, costs)); }}// This code is contributed by akshitaguprzj3 |
Python3
# Python program for the above approachdef min_cost(days, costs): q_month = [] # queue for monthly workers q_week = [] # queue for weekly workers ans = 0 # loop over days array for day in days: # Step1: remove expired days from both queues while q_month and q_month[0][0] + 30 <= day: q_month.pop(0) while q_week and q_week[0][0] + 7 <= day: q_week.pop(0) # Step2: add current day's cost q_month.append((day, ans + costs[2])) q_week.append((day, ans + costs[1])) # Step3: Update ans ans = min(ans + costs[0], min(q_month[0][1], q_week[0][1])) return ans#Driver codeif __name__ == "__main__": days = [2, 4, 6, 7, 8, 10, 15] costs = [3, 108, 20] print(min_cost(days, costs)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ public static int MinCost(List<int> days, List<int> costs) { List<(int day, int cost)> qMonth = new List<(int, int)>(); // queue for monthly workers List<(int day, int cost)> qWeek = new List<(int, int)>(); // queue for weekly workers int ans = 0; // loop over days array foreach (int day in days) { // remove expired days from both queues while (qMonth.Count > 0 && qMonth[0].day + 30 <= day) { qMonth.RemoveAt(0); } while (qWeek.Count > 0 && qWeek[0].day + 7 <= day) { qWeek.RemoveAt(0); } // add current day's cost qMonth.Add((day, ans + costs[2])); qWeek.Add((day, ans + costs[1])); // Update ans ans = Math.Min(ans + costs[0], Math.Min(qMonth[0].cost, qWeek[0].cost)); } return ans; } // Driver code public static void Main(string[] args) { List<int> days = new List<int> { 2, 4, 6, 7, 8, 10, 15 }; List<int> costs = new List<int> { 3, 108, 20 }; Console.WriteLine(MinCost(days, costs)); }} |
Javascript
function minCost(days, costs) { const qMonth = []; const qWeek = []; // Don't initialize with Infinity, otherwise ans will go // in negative range (i.e., the wrong answer will be obtained) let ans = 0; // Loop over days array for (const day of days) { /* Below is the intuition behind using a queue in this question */ // Step 1: Remove expired days from both queues while (qMonth.length > 0 && qMonth[0][0] + 30 <= day) { qMonth.shift(); } while (qWeek.length > 0 && qWeek[0][0] + 7 <= day) { qWeek.shift(); } // Step 2: Add current day's cost qMonth.push([day, ans + costs[2]]); qWeek.push([day, ans + costs[1]]); // Step 3: Update ans ans = Math.min(ans + costs[0], Math.min(qMonth[0][1], qWeek[0][1])); } return ans;}// Driver Codeconst arr = [2, 4, 6, 7, 8, 10, 15];const cost = [3, 108, 20];console.log(minCost(arr, cost));// This code is contributed by shivamgupta310570 |
Output
20
Time complexity: O(N)
AuxilairySpace: O(1)
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!