算法2026-04-15·6 分钟

算法知识库：贪心算法实现

JavaScript/TypeScript 实现经典贪心算法，如区间调度、跳跃游戏等。

贪心算法实现

1. 区间调度

ts

function intervalScheduling(intervals: [number, number][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0;
  let end = -Infinity;

  for (const [start, finish] of intervals) {
    if (start >= end) {
      count += 1;
      end = finish;
    }
  }

  return count;
}

2. 跳跃游戏

ts

function canJump(nums: number[]): boolean {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i += 1) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return true;
}

3. 买卖股票的最佳时机

ts

function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

4. 分发饼干

ts

function findContentChildren(g: number[], s: number[]): number {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let i = 0;
  let j = 0;

  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) {
      i += 1;
    }
    j += 1;
  }

  return i;
}

5. 实现要点

贪心选择当前最优解。
适用于具有贪心选择性质的问题。
通常需要排序或预处理。

算法贪心JavaScript