Greedy Fundamentals & Intervals

  • Prove greedy choice property
  • Use exchange or stays-ahead arguments
1 / 4

Interval scheduling

  • Sort by end time
  • Pick earliest finish, skip overlaps
  • O(n log n)
2 / 4

Optimal merge

  • Always merge two smallest
  • Min-heap implementation
  • Same idea as Huffman coding
3 / 4

Pitfalls

  • Wrong sort key
  • No proof
  • Tie handling matters
4 / 4
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.