Показать сообщение отдельно
  #11 (permalink)  
Старый 24.05.2021, 10:22
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,012

Запилил решение. Вспомнил реализацию 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
    }
  }
}

Последний раз редактировалось Alexandroppolus, 25.05.2021 в 22:32.
Ответить с цитированием