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!
