贪心 | Live Note

遵循某种策略，不断地选取当前最优策略的算法设计方法。

代码实现：

/**
 * * @param {number[]} coins - The coins already have.
 * @param {number} target - Target currency.
 * @return {number} - The minimum count of coins used.
 */ function resolve(coins, target) {
  const coinAmount = [1, 5, 10, 50, 100, 500]
  let result = 0

  for (let i = 5; i >= 0; i--) {
    const num = Math.min(Math.floor(target / coinAmount[i]), coins[i]) // 拿最大的数量
    target -= num * coinAmount[i]
    result += num
  }

  return result
}

console.log(resolve([3, 2, 1, 3, 0, 2], 620))

eg：区间问题

代码实现：

/**
 * @param {number[]} start - Start time of the each job.
 * @param {number[]} end - End time of the each job.
 * @return {number} - The maximum of jobs can be done.
 */ function resolve(start, end) {
  let result = 0
  let t = 0 // current time
  const arr = [] // [end, start]

  start.map((_, index) => {
    arr.push([end[index], start[index]])
  })

  // 按照字典序进行升序
  arr.sort(([a1, a2], [b1, b2]) => {
    if (a1 !== b1) return a1 - b1
    return a2 - b2
  })

  for (let i = 0, len = arr.length; i < len; i++) {
    const [end, start] = arr[i]

    if (t < start) {
      result++ // 任务数 + 1      t = end // 当前时间更新为任务结束时间
    }
  }

  return result
}

console.log(resolve([1, 2, 4, 6, 8], [3, 5, 7, 9, 10]))

目录