Last Updated: 17 Mar, 2021

Maximum Number Of Eaten Apples

Moderate

Asked in companies

Solve now

Problem statement

You are given two arrays, each of size ‘N’. The first array named ‘APPLES’ denotes the count of the apples produced by an apple tree on each day for N days. The second array named ‘DAYS’ represents the number of days after which these apples will become inedible.

Your task is to find the maximum number of apples you can eat if you decided to eat at most one apple per day.

Note :

1) It is also possible that the tree doesn’t grow any apples on any particular day, i.e., ’APPLES[i]’ = 0 for ‘i’th day.
2) ‘DAYS[i]’ = 0 if and only if ‘APPLES[i]’ = 0.
3) You can keep eating apples even after ‘N’ days, but keep in mind that you can eat at most one apple per day.

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a positive integer ‘N’ denoting the size of the arrays.

The second line of each test case contains N space-separated non-negative integers denoting the elements of the array ‘APPLES’.

The third line of each test case contains N space-separated non-negative integers denoting the elements of the array ‘DAYS’.

Output Format :

For each test case, print the maximum number of apples you can eat.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 3000
0 <= ‘APPLES[i]’, ‘DAYS[i]’  <= 3000  

Where 'APPLE[i]' and 'DAYS[i]' denotes the ith element of respective array.  

Time Limit: 1sec

Solve now

Approaches

01 Approach

The idea here is to eat the apples that become inedible first than those who become inedible last. For this, we need a structure to keep the apples sorted according to their finish time. We need counts and the expiry date of all apples. Which data structure can we use to tackle this kind of scenario? Yes, you are absolutely right. The answer is a priority queue. Initialize a min priority queue to store the count and the expiry date of apples produced on ‘i’th day. Now, start inserting the count and the expiration date of the apples produced on the ‘i’th day. After insertion, we have to remove those apples that have expired already from the priority queue. Then just add 1 to the answer and decrement the count of the top apple of the priority queue it is not empty.

Steps:

As we need count and the expiry date of apples together so, we can use a pair.
Initialize a min priority queue named pq to store the pair. The 1st element of the pair is the expiration date and 2nd is the count of the ‘i’th apples.
Declare two variables named i = 0, and ans = 0.
Run a while loop until any of the 2 conditions are true that are i < ‘N’ or pq is not empty and in each iteration do:
- If ‘i’ < ‘N’ and ‘APPLES[i]’ not 0, then push the pair {i+’DAYS[i]’-1, ‘APPLES[i]’} in the pq which is nothing but the expiration date and the count of apples produced on the ‘i’th day.
- Run a while loop until both the conditions are true: pq is not empty and pq.top().first expired, in each iteration:
  - Pop the top element from the pq.
- If pq not empty, then:
  - Increment the ans by 1.
  - Take the top element in the variable temp, temp = pq.top().
  - Pop the top element, pq.pop().
  - If temp.second > 1, then insert it again after the decrementation in its count, i.e., pq.insert({temp.first, temp.second-1}).
- Increment i by 1.
Finally, return ans.

Solve now