Greedy Patterns

This file lists commonly used greedy patterns for DSA problems, along with keywords, detection cues, and when to use them. Once you read this deeply, the keywords and input structures should stay in your mind as a mental map for identifying greedy problems efficiently. Focus on recognizing the input structure (arrays, intervals, weights) and keywords (start, end, value, weight, fraction, min/max, schedule).

Greedy patterns are most suitable when local optimal choices lead to global optimum, often combined with sorting, priority queues, or linear scans. Recognize the problem type and the structure first—then the greedy approach becomes intuitive.

---

Pattern Table (Simplified & Prioritized, 4 Columns)

Pattern	Typical Question Types	Keywords / Detection Cues	Notes / When to Use
Activity Selection / Interval Scheduling	Max non-overlapping intervals	start, end, schedule	Greedy by earliest end time; input: array of intervals; pick interval that leaves max space for others.
Minimum Spanning Tree (Prim/Kruskal)	Connect all nodes with minimum total cost	MST, min cost, edge	Pick smallest edges without forming cycles; input: weighted graph (edge list or adjacency).
Coin Change (Greedy)	Min coins to make given amount	coin, min, change	Works when denominations are canonical; input: array of coin values; pick largest first.
Huffman Encoding	Min cost encoding, Compression	frequency, priority	Greedy by lowest frequencies; input: array of symbols with weights; build tree using min-heap.
Geometry / Line / Angle Problems	Intersections, Convex hull, Points	line, point, angle	Sort and use slopes/cross product; input: array of points or lines; local choice leads to global geometry solution.
Fractional Knapsack	Max value under capacity	weight, value, fraction	Pick items by value/weight ratio; input: array of weights & values; take fraction if needed.
Interval Merging / Skyline	Merge overlapping intervals, Max overlap	start, end, height	Sort by start/end and greedily merge; input: array of intervals; linear scan solves efficiently.

---

1. Activity Selection / Interval Scheduling – Common (Arrays / Intervals)

When to use / Detection cues:

• Input structure: Array of intervals [start, end].
• Question keywords: start, end, schedule, non-overlapping, maximum.
• Problem hints: Maximize number of non-overlapping intervals, select tasks without conflict.
• Why it works: Choose the earliest finishing interval at each step. Local optimal choice ensures global maximum.

Typical questions:

• Maximum number of non-overlapping meetings
• Select tasks to maximize number of activities

Mental trigger: “Schedule” + “maximize non-overlapping intervals” → Activity Selection.

---

2. Minimum Spanning Tree (Prim/Kruskal) – Common (Graph only)

When to use / Detection cues:

• Input structure: Weighted undirected graph, edge list or adjacency.
• Question keywords: MST, minimum cost, connect all nodes, total weight.
• Problem hints: Connect all vertices with minimum total edge cost without cycles.
• Why it works: Greedy choice of smallest edge that does not form a cycle builds MST. Kruskal uses Union-Find, Prim uses priority queue.

Typical questions:

• Minimum cost to connect cities
• Kruskal’s MST, Prim’s MST

Mental trigger: “Connect all nodes with minimum cost” → MST.

---

3. Coin Change (Greedy) – Common (Arrays / Math)

When to use / Detection cues:

• Input structure: Array of coin denominations.
• Question keywords: coin, min, change, make amount.
• Problem hints: Find minimum number of coins to make a target amount.
• Why it works: Pick the largest coin denomination possible first. Only works when coins are canonical (e.g., 1,2,5,10).

Typical questions:

• Min number of coins for amount N
• Currency change problems

Mental trigger: “Min coins” + “largest first” → Greedy Coin Change.

---

4. Huffman Encoding – Rare / Bonus (Heap / Strings)

When to use / Detection cues:

• Input structure: Array of symbols with frequency/weight.
• Question keywords: frequency, priority, encoding, compression.
• Problem hints: Build min-cost prefix-free code for symbols.
• Why it works: Always merge two smallest frequency nodes; local greedy choice gives global minimal cost. Use min-heap.

Typical questions:

• Construct Huffman tree
• Minimum cost encoding for symbols

Mental trigger: “Lowest frequency merge” + “prefix-free code” → Huffman.

---

5. Geometry / Line / Angle Problems – Rare / Bonus (Math / Geometry)

When to use / Detection cues:

• Input structure: Array of points, lines, or angles.
• Question keywords: line, point, angle, slope, convex hull.
• Problem hints: Find intersections, hulls, or maximal/minimal geometric properties.
• Why it works: Greedy based on slopes, cross products, or sorting points ensures optimal selections.

Typical questions:

• Convex hull (Graham scan)
• Max points on a line
• Count intersections

Mental trigger: “Line/angle/point” + “sort/slopes” → Geometry Greedy.

---

6. Fractional Knapsack – Common (Arrays)

When to use / Detection cues:

• Input structure: Array of items with weight and value; fractional allowed.
• Question keywords: weight, value, fraction, maximize.
• Problem hints: Maximize value under capacity constraints; fractions allowed.
• Why it works: Pick items with highest value/weight ratio first; local optimal ratio ensures global maximum.

Typical questions:

• Max profit under weight capacity
• Fractional knapsack

Mental trigger: “Max value/weight ratio” → Fractional Knapsack.

---

7. Interval Merging / Skyline – Common (Arrays / Intervals)

When to use / Detection cues:

• Input structure: Array of intervals [start, end, height].
• Question keywords: merge, start, end, height, skyline, overlap.
• Problem hints: Merge overlapping intervals or build skyline; maintain maximal properties.
• Why it works: Sort by start (or end), then merge or sweep line; greedy selection ensures correct combination.

Typical questions:

• Merge overlapping intervals
• Skyline problem
• Max overlap of intervals

Mental trigger: “Sort intervals + merge/greedy” → Interval Merging / Skyline.

---

Mini Notes / Tips

### Tips

- Always identify the **input structure**: arrays, intervals, weights, points, or frequencies.
- Look for **keywords**: start, end, schedule, min/max, coin, value, weight, fraction, height.
- Greedy works when **local optimal choice guarantees global optimum**.
- Sorting is frequently the **first preprocessing step**.
- Intervals: sort by end/start. Coins/weights: pick largest or highest ratio. Huffman: pick smallest frequencies.
- Rare patterns like Huffman or Geometry require **priority queue** or **cross-product** knowledge.
- After reading once, try to recall **input → keywords → local choice → global solution** for each pattern.