Maximum Number Of Eaten Apples

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.

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’.

You can eat 6 apples as follows: On the 1st day, you can eat the apple produced by the tree on day 1. On the 2nd day, you can eat the apple produced by the tree on day 2. On the 3rd day, you can eat the apple produced by the tree on day 2. From the 4th to the 6th day, you can eat the apple produced by the tree on day 4.

You can eat 3 apples as follows: On the 1st day, you can eat the apple produced by the tree on day 1. On the 2nd day, you can eat the apple produced by the tree on day 1. On the 3rd day, you can eat the apple produced by the tree on day 3. After this day, we are having 1 more apple but it becomes inedible on the 4th day.

Priority Queue Based 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.

Time Complexity

O(N*logN), where ‘N’ is the size of both arrays.

We are running a loop to traverse the arrays whose size is ‘N’, and also doing the priority queue operations that take log(N) time. Hence the overall time complexity will be O(N*logN).

Space Complexity

O(N), where ‘N’ is the size of both arrays.

As we are creating a priority queue to store the elements of the array, and the size of the array is N. Hence, the space complexity will be O(N).

Maximum Number Of Eaten Apples

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation For Sample Input 2 :

Steps: