Greedy

Master greedy algorithms by making locally optimal choices to find globally optimal solutions.

Showing 6 of 6 questions
Easy: 0 Medium: 0 Hard: 0
QUESTIONDIFFICULTY
Gas Station
Determine the starting gas station index to complete a circular tour
Medium
Jump Game
Determine if you can reach the last index given maximum jump lengths
Medium
Jump Game II
Find the minimum number of jumps to reach the last index
Medium
Task Scheduler
Find minimum intervals to execute all tasks with cooldown between identical tasks
Medium
Minimum Number of Platforms
Find minimum platforms required at a railway station given arrival and departure times
Medium
Candy
Distribute minimum candies to children so higher-rated children get more than neighbors
Hard

Overview

Greedy algorithms make the locally optimal choice at each step with the hope of finding the globally optimal solution. This section covers greedy strategies for scheduling, interval, and optimization problems.

Key Concepts

  • Greedy choice property
  • Optimal substructure
  • Activity selection and scheduling
  • Interval problems
  • Two-pass greedy strategies
  • Proof of correctness (exchange argument)

Common Problems

Medium

  • Jump Game
  • Jump Game II
  • Gas Station
  • Task Scheduler
  • Minimum Number of Platforms

Hard

  • Candy
  • Minimum Number of Arrows to Burst Balloons
  • Non-overlapping Intervals

Practice Tips

  1. Prove greedy works: Use exchange argument or show greedy stays ahead
  2. Sort first: Many greedy problems require sorting the input
  3. Consider counterexamples: Before committing to greedy, check if it fails
  4. Compare with DP: If greedy doesn’t work, try dynamic programming

Resources