跳转至

贪心

Introduction

Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. They are widely used for optimization problems where choosing the best option at each stage leads to an overall optimal solution.

Typical Applications

  • Interval scheduling (e.g., activity selection)
  • Coin change (when denominations are canonical)
  • Huffman coding
  • Minimum spanning tree (Kruskal, Prim)
  • Dijkstra's shortest path (with non-negative weights)
  • Task assignment and resource allocation
  • String and array problems (e.g., jump game, partitioning)

Classic Problems

Greedy Solution Template

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Example: Interval scheduling
func greedySolve(intervals [][]int) int {
    // Sort intervals by end time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    count, end := 0, math.MinInt32
    for _, interval := range intervals {
        if interval[0] >= end {
            count++
            end = interval[1]
        }
    }
    return count
}

Key Points & Pitfalls

  • Greedy choice must be proven to lead to global optimum (often via exchange argument or proof by contradiction)
  • Not all problems with local choices are suitable for greedy; always check for counterexamples
  • Sorting is often a key step in greedy solutions
  • Sometimes multiple greedy strategies exist; test and prove correctness

References