Запилил решение. Вспомнил реализацию heap
function eatenApples(counts, days) {
if (!counts || !counts.length) {
return 0
}
let result = 0
const heap = createHeap(counts.length, (a, b) => a.expire < b.expire)
for (let day = 0; day < counts.length || heap.getLength(); ++day) {
// выкидываем устаревшие
while (heap.getLength() && heap.getTop().expire <= day) {
heap.pop()
}
const count = day < counts.length ? counts[day] : 0
if (count > 0) {
// если есть новая порция, добавляем в очередь
heap.push({ count, expire: day + Math.max(days[day], 1) })
}
// если очередь не пустая, берем одно из корзины с самыми скоропортящимися
const top = heap.getTop()
if (top) {
result++
top.count--
// если оная корзина опустела, выкидываем
if (top.count < 1) {
heap.pop()
}
}
}
return result
}
alert([
eatenApples([1,2,3,5,2], [3,2,1,4,2]),
eatenApples([3,0,0,0,0,2], [3,0,0,0,0,2]),
eatenApples([6, 1, 1], [16, 1, 1])
].join('\n'));
//--------------------------------------------------------
// heap
function createHeap(maxSize, fnIsPrior) {
const arr = new Array(maxSize)
let length = 0
return {
getLength() {
return length
},
getTop() {
return length ? arr[0] : undefined
},
push(data) {
if (length === maxSize) {
return
}
let i = length
for (let p = Math.floor((i - 1) / 2); i > 0 && fnIsPrior(data, arr[p]); i = p, p = Math.floor((p - 1) / 2)) {
arr[i] = arr[p]
}
arr[i] = data
length++
},
pop() {
if (!length) {
return undefined
}
const r = arr[0]
length--
const value = arr[length]
arr[length] = undefined
if (length) {
let i = 0
while (true) {
let childIdx = i * 2 + 1
if (childIdx < length) {
if (childIdx + 1 < length && fnIsPrior(arr[childIdx + 1], arr[childIdx])) {
childIdx++
}
if (fnIsPrior(arr[childIdx], value)) {
arr[i] = arr[childIdx]
i = childIdx
} else {
break
}
} else {
break
}
}
arr[i] = value
}
return r
}
}
}
