Maximum Number of Eaten Apples
Problem Statement
There is a special kind of apple tree that grows apples every day for n days. On the ith day, the tree grows apples[i] apples that will rot after days[i] days. You can eat at most one apple per day. You may keep eating apples after the first n days if some apples have not rotted yet. Return the maximum number of apples you can eat.
Examples
Example 1
Input:
apples = [1,2,3,5,2], days = [3,2,3,3,3]
Output:
7
Explanation:
- Day 1: Grow 1 apple, eat 1 apple. (1 apple left, 2 days to rot)
- Day 2: Grow 2 apples, eat 1 apple. (3 apples left, 1 day to rot)
- Day 3: Grow 3 apples, eat 1 apple. (5 apples left, 3 days to rot)
- Day 4: Grow 5 apples, eat 1 apple. (9 apples left, 2 days to rot)
- Day 5: Grow 2 apples, eat 2 apples. (9 apples left, 1 day to rot)
- Day 6: Eat 1 apple. (8 apples left, 0 days to rot)
- Total eaten apples: 7
Example 2
Input:
apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output:
5
Explanation:
- Day 1: Grow 3 apples, eat 1 apple. (2 apples left, 2 days to rot)
- Day 2: Grow 0 apples, eat 1 apple. (1 apple left, 1 day to rot)
- Day 3: Grow 0 apples, eat 1 apple. (0 apples left, 0 days to rot)
- Day 4: Grow 0 apples, eat 0 apples. (0 apples left, 0 days to rot)
- Day 5: Grow 0 apples, eat 0 apples. (0 apples left, 0 days to rot)
- Day 6: Grow 2 apples, eat 2 apples. (0 apples left, 2 days to rot)
- Total eaten apples: 5
Constraints
1 <= n <= 2 * 10^50 <= apples[i] <= 2 * 10^51 <= days[i] <= 2 * 10^5
Hints
- Use a priority queue to keep track of the apples that will rot soon.
- Always eat the apple that will rot the soonest.
- If there are no apples that will rot soon, eat a new apple from the tree.