1705. Maximum Number of Eaten Apples #

Problem #

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, that is on day i + days[i] the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any apples, which are denoted by apples[i] == 0 and days[i] == 0.

You decided to eat at most one apple a day (to keep the doctors away). Note that you can keep eating after the first n days.

Given two integer arrays days and apples of length n, return the maximum number of apples you can eat.

Example 1:

Input: apples = [1,2,3,5,2], days = [3,2,1,4,2]
Output: 7
Explanation: You can eat 7 apples:
- On the first day, you eat an apple that grew on the first day.
- On the second day, you eat an apple that grew on the second day.
- On the third day, you eat an apple that grew on the second day. After this day, the apples that grew on the third day rot.
- On the fourth to the seventh days, you eat apples that grew on the fourth day.

Example 2:

Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5
Explanation: You can eat 5 apples:
- On the first to the third day you eat apples that grew on the first day.
- Do nothing on the fouth and fifth days.
- On the sixth and seventh days you eat apples that grew on the sixth day.

Constraints:

• apples.length == n
• days.length == n
• 1 <= n <= 2 * 10000
• 0 <= apples[i], days[i] <= 2 * 10000
• days[i] = 0 if and only if apples[i] = 0.

Problem Summary #

There is a special apple tree that can grow several apples every day for n consecutive days. On day i, the tree grows apples[i] apples. These apples will rot after days[i] days (that is, on day i + days[i]) and become inedible. There may also be some days when no new apples grow on the tree, represented by apples[i] == 0 and days[i] == 0.

You plan to eat at most one apple per day to maintain a balanced diet. Note that you can continue eating apples after these n days.

Given two integer arrays days and apples of length n, return the maximum number of apples you can eat.

Solution Approach #

Greedy algorithm and min-heap

• In data, end represents the rotting date, and left represents the number of apples remaining
• Greedy: eat the apple with the smallest end that has not rotted each day
• Min-heap: construct a min-heap whose type is an array (the element type in the array is data)

Code #

package leetcode

import "container/heap"

func eatenApples(apples []int, days []int) int {
	h := hp{}
	i := 0
	var ans int
	for ; i < len(apples); i++ {
		for len(h) > 0 && h[0].end <= i {
			heap.Pop(&h)
		}
		if apples[i] > 0 {
			heap.Push(&h, data{apples[i], i + days[i]})
		}
		if len(h) > 0 {
			minData := heap.Pop(&h).(data)
			ans++
			if minData.left > 1 {
				heap.Push(&h, data{minData.left - 1, minData.end})
			}
		}
	}
	for len(h) > 0 {
		for len(h) > 0 && h[0].end <= i {
			heap.Pop(&h)
		}
		if len(h) == 0 {
			break
		}
		minData := heap.Pop(&h).(data)
		nums := min(minData.left, minData.end-i)
		ans += nums
		i += nums
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

type data struct {
	left int
	end  int
}

type hp []data

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].end < h[j].end }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *hp) Push(x interface{}) {
	*h = append(*h, x.(data))
}

func (h *hp) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}