Given two arrays apples[] and days[] representing the count of apples an apple tree produces and the number of days these apples are edible from the ith day respectively, the task is to find the maximum number of apples a person can eat if the person can eat at most one apple in a day.
Examples
Input: apples[] = { 1, 2, 3, 5, 2 }, days[] = { 3, 2, 1, 4, 2 }
Output: 7
Explanation:
On 1st day, person eats the apple produced by apple tree on the 1st day.
On 2nd day, person eats the apple produced by apple tree on the 2nd day.
On 3rd day, person eats the apple produced by apple tree on the 2nd day.
On 4th to 7th day, person eats the apple produced by apple tree on the 4th day.Input: apples[] = { 3, 0, 0, 0, 0, 2 }, days[] = { 3, 0, 0, 0, 0, 2 }
Output: 5
Approach: The idea is to eat the apples having the closest expiration date. Follow the steps below to solve the problem:
- Initialize a priority_queue to store the count of apples produced on the ith day and the expiration date of those apples.
- Traverse both the arrays and insert the count of apples and the expiration date of those apples produced by the apple tree on the ith day.
- Check if expiration date of the top element of the priority_queue has expired or not. If found to be true, then pop the elements from the priority_queue.
- Otherwise, increment the maximum count and decrement the count of apples from the priority_queue.
- Finally, print the maximum count obtained.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number of apples// a person can eat such that the person eat// at most one apple in a day.int cntMaxApples(vector<int> apples, vector<int> days){ // Stores count of apples and number // of days those apples are edible typedef pair<int, int> P; // Store count of apples and number // of days those apples are edible priority_queue<P, vector <P>, greater <P> > pq; // Stores indices of the array int i = 0; // Stores count of days int n = apples.size(); // Stores maximum count of // edible apples int total_apples = 0; // Traverse both the arrays while (i < n || !pq.empty()) { // If top element of the apple // is not already expired if (i < n && apples[i] != 0) { // Insert count of apples and // their expiration date pq.push({ i + days[i] - 1, apples[i] }); } // Remove outdated apples while (!pq.empty() && pq.top().first < i) { pq.pop(); } // Insert all the apples produces by // tree on current day if (!pq.empty()) { // Stores top element of pq auto curr = pq.top(); // Remove top element of pq pq.pop(); // If count of apples in curr // is greater than 0 if (curr.second > 1) { // Insert count of apples and // their expiration date pq.push({ curr.first, curr.second - 1 }); } // Update total_apples ++total_apples; } // Update index ++i; } return total_apples;}// Driver Codeint main(){ vector<int> apples = { 1, 2, 3, 5, 2 }; vector<int> days = { 3, 2, 1, 4, 2 }; cout << cntMaxApples(apples, days); return 0;} |
Java
// Java program of the above approachimport java.util.*;// Function to find the maximum number of apples// a person can eat such that the person eat// at most one apple in a day.class GFG { static int cntMaxApples(int[] apples, int[] days) { // Stores count of apples and number // of days those apples are edible class Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; } } // Store count of apples and number // of days those apples are edible PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.first - b.first); // Stores indices of the array int i = 0; // Stores count of days int n = apples.length; // Stores maximum count of // edible apples int total_apples = 0; // Traverse both the arrays while (i < n || !pq.isEmpty()) { // If top element of the apple // is not already expired if (i < n && apples[i] != 0) { // Insert count of apples and // their expiration date pq.add(new Pair(i + days[i] - 1, apples[i])); } // Remove outdated apples while (!pq.isEmpty() && pq.peek().first < i) { pq.remove(); } // Insert all the apples produces by // tree on current day if (!pq.isEmpty()) { // Stores top element of pq Pair curr = pq.peek(); // Remove top element of pq pq.remove(); // If count of apples in curr // is greater than 0 if (curr.second > 1) { // Insert count of apples and // their expiration date pq.add(new Pair(curr.first, curr.second - 1)); } // Update total_apples ++total_apples; } // Update index ++i; } return total_apples; } // Driver Code public static void main(String[] args) { int[] apples = { 1, 2, 3, 5, 2 }; int[] days = { 3, 2, 1, 4, 2 }; System.out.println(cntMaxApples(apples, days)); }}// This code is contributed by ishankhandelwals. |
Python3
# Python3 program of the above approach# Function to find the maximum number of apples # a person can eat such that the person eat # at most one apple in a day. def cntMaxApples(apples, days) : # Store count of apples and number # of days those apples are edible pq = [] # Stores indices of the array i = 0 # Stores count of days n = len(apples) # Stores maximum count of # edible apples total_apples = 0 # Traverse both the arrays while (i < n or len(pq) > 0) : # If top element of the apple # is not already expired if (i < n and apples[i] != 0) : # Insert count of apples and # their expiration date pq.append([i + days[i] - 1, apples[i]]) pq.sort() # Remove outdated apples while (len(pq) > 0 and pq[0][0] < i) : pq.pop(0) # Insert all the apples produces by # tree on current day if (len(pq) > 0) : # Stores top element of pq curr = pq[0] # Remove top element of pq pq.pop(0) # If count of apples in curr # is greater than 0 if (len(curr) > 1) : # Insert count of apples and # their expiration date pq.append([curr[0], curr[1] - 1]) pq.sort() # Update total_apples total_apples += 1 # Update index i += 1 return total_apples apples = [ 1, 2, 3, 5, 2 ] days = [ 3, 2, 1, 4, 2 ]print(cntMaxApples(apples, days))# This code is contributed by divyesh072019 |
C#
// C# program of the above approach using System;using System.Collections.Generic;class GFG { // Function to find the maximum number of apples // a person can eat such that the person eat // at most one apple in a day. static int cntMaxApples(int[] apples, int[] days) { // Store count of apples and number // of days those apples are edible List<Tuple<int,int>> pq = new List<Tuple<int,int>>(); // Stores indices of the array int i = 0; // Stores count of days int n = apples.Length; // Stores maximum count of // edible apples int total_apples = 0; // Traverse both the arrays while (i < n || pq.Count > 0) { // If top element of the apple // is not already expired if (i < n && apples[i] != 0) { // Insert count of apples and // their expiration date pq.Add(new Tuple<int,int>(i + days[i] - 1, apples[i])); pq.Sort(); } // Remove outdated apples while (pq.Count > 0 && pq[0].Item1 < i) { pq.RemoveAt(0); } // Insert all the apples produces by // tree on current day if (pq.Count > 0) { // Stores top element of pq Tuple<int,int> curr = pq[0]; // Remove top element of pq pq.RemoveAt(0); // If count of apples in curr // is greater than 0 if (curr.Item2 > 1) { // Insert count of apples and // their expiration date pq.Add(new Tuple<int,int>(curr.Item1, curr.Item2 - 1)); pq.Sort(); } // Update total_apples ++total_apples; } // Update index ++i; } return total_apples; } // Driver code static void Main() { int[] apples = { 1, 2, 3, 5, 2 }; int[] days = { 3, 2, 1, 4, 2 }; Console.Write(cntMaxApples(apples, days)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// Javascript program of the above approach// Function to find the maximum number of apples // a person can eat such that the person eat // at most one apple in a day. function cntMaxApples(apples, days) { // Store count of apples and number // of days those apples are edible let pq = [] // Stores indices of the array let i = 0 // Stores count of days let n = apples.length; // Stores maximum count of // edible apples let total_apples = 0 // Traverse both the arrays while (i < n || pq.length > 0) { // If top element of the apple // is not already expired if (i < n && apples[i] != 0) { // Insert count of apples and // their expiration date pq.push([i + days[i] - 1, apples[i]]) pq.sort() } // Remove outdated apples while (pq.length > 0 && pq[0][0] < i) { pq.shift() } // Insert all the apples produces by // tree on current day if (pq.length > 0) { // Stores top element of pq curr = pq[0] // Remove top element of pq pq.shift() // If count of apples in curr // is greater than 0 if (curr.length > 1) { // Insert count of apples and // their expiration date pq.push([curr[0], curr[1] - 1]) pq.sort() } // Update total_apples total_apples += 1 } // Update index i += 1 } return total_apples}let apples = [1, 2, 3, 5, 2]let days = [3, 2, 1, 4, 2]document.write(cntMaxApples(apples, days))// This code is contributed by Saurabh Jaiswal</script> |
Output
7
Time Complexity: O(N log N)
Auxiliary Space: O(N)
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!
