- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have two arrays called days and apples of same length n. There is a special kind of apple tree that grows apples every day for n consecutive days. On the ith day, it grows apples[i] number of apples and that will rot after days[i] days, so we can say it like that on day i + days[i] the apples will be rotten and cannot be eaten. On some days. If apples[i] = 0, and days[i] = 0, then it indicates on day i, the apple tree is not growing any apple. We can take at most one apple a day. (We can keep eating after the first n days). Here we have to find the maximum number of apples we can eat.

So, if the input is like apples = [1,2,3,5,2] days = [3,2,1,4,2], then the output will be 7 because −

On day 1, we eat an apple that grew on the first day.

On day 2, we eat an apple that grew on the second day.

On day 3, we eat an apple that grew on the second day. But after this day, the apples that grew on the third day will rot.

On days from 4 to 7, we eat apples that grew on the fourth day.

To solve this, we will follow these steps −

- minheap := a new empty heap
- day := 0, res := 0
- for i in range 0 to size of apples - 1, do
- day := i
- while minheap is not empty and rot value of top of minheap − day, do
- remove top element from minheap

- nbrApple := apples[i]
- expiration := i + days[i]-1
- if nbrApple > 0, then
- insert (expiration, nbrApple) pair into minheap

- if minheap is not empty, then
- (date, apple) := top element of minheap and remove it from heap
- res := res + 1
- if apple > 1, then
- insert (date, apple-1) pair into minheap

- while minheap is not empty, do
- day := day + 1
- while minheap is not empty and rot value of top of minheap < day, do
- remove top element from minheap

- if minheap is empty, then
- come out from loop

- (date, apple) := top of minheap and remove it from heap
- res := res + 1
- if apple > 1, then
- insert (date, apple-1) pair into minheap

- return res

Let us see the following implementation to get better understanding −

import heapq def solve(apples, days): minheap = [] heapq.heapify(minheap) day = 0 res = 0 for i in range(len(apples)): day = i while minheap and minheap[0][0] < day: heapq.heappop(minheap) nbrApple = apples[i] expiration = i + days[i]-1 if nbrApple > 0: heapq.heappush(minheap, (expiration, nbrApple)) if minheap: date, apple = heapq.heappop(minheap) res += 1 if apple > 1: heapq.heappush(minheap, (date, apple-1)) while minheap: day += 1 while minheap and minheap[0][0] < day: heapq.heappop(minheap) if minheap == []: break date, apple = heapq.heappop(minheap) res += 1 if apple > 1: heapq.heappush(minheap, (date, apple-1)) return res apples = [1,2,3,5,2] days = [3,2,1,4,2] print(solve(apples, days))

[1,2,3,5,2],[3,2,1,4,2]

7

- Related Questions & Answers
- Program to find maximum number of non-overlapping substrings in Python
- Program to find maximum number of balanced groups of parentheses in Python
- Program to find maximum number of coins we can collect in Python
- Program to find maximum number of balls in a box using Python
- Program to find maximum number of groups getting fresh donuts in Python
- Program to find number of columns flips to get maximum number of equal Rows in Python?
- Program to find maximum number of coins we can get using Python
- Program to find maximum difference of any number and its next smaller number in Python
- Program to find maximum number of consecutive values you can make in Python
- Program to find maximum number of people we can make happy in Python
- C++ Program to Find Maximum Number of Edge Disjoint Paths
- Find the maximum number of composite summands of a number in Python
- Python program to find the maximum of three numbers
- Program to find maximum product of contiguous subarray in Python
- Program to find maximum sum of multiplied numbers in Python

Advertisements