Wrong Sorting Criterion: The #1 Greedy Mistake (And How to Fix It)

You write a greedy solution. You sort the array. You submit. Wrong Answer.

The problem? You sorted by the wrong key. This is the #1 greedy mistake, and it's surprisingly easy to make.

This guide teaches you how to choose the right sorting criterion, common mistakes, and a systematic framework that works every time.

TL;DR

Common mistakes:

• ❌ Sorting by start time instead of end time (interval scheduling)
• ❌ Sorting by value instead of ratio (knapsack)
• ❌ Sorting by one attribute when you need difference (two city scheduling)

How to choose:

1. Think: "What makes an element better for greedy?"
2. Test with small examples
3. Verify with proof or counterexample

The Mistake: Sorting by the Wrong Key

Example 1: Interval Scheduling

❌ Wrong:

intervals.sort(key=lambda x: x[0])  # Start time

✅ Correct:

intervals.sort(key=lambda x: x[1])  # End time

Why it matters:

Intervals: [(1,10), (2,3), (4,5)]

Sort by start: [(1,10), (2,3), (4,5)]
  Pick (1,10) → blocks (2,3) and (4,5)
  Result: 1 interval ✗

Sort by end: [(2,3), (4,5), (1,10)]
  Pick (2,3), (4,5)
  Result: 2 intervals ✓

Example 2: Two City Scheduling

❌ Wrong:

costs.sort(key=lambda x: x[0])  # Cost to city A

✅ Correct:

costs.sort(key=lambda x: x[0] - x[1])  # Difference

Why it matters:

Costs: [[10,20], [30,200], [400,50], [30,20]]

Sort by costA: [[10,20], [30,200], [30,20], [400,50]]
  Send first 2 to A: 10+30=40
  Send last 2 to B: 20+50=70
  Total: 110 ✓ (happens to work)

Sort by difference: [[10,20], [30,20], [400,50], [30,200]]
  Send first 2 to A: 10+30=40
  Send last 2 to B: 50+200=250
  Total: 290 ✗ (WRONG!)

Wait, let me recalculate...
Actually, sort by difference (costA - costB):
  [10,20]: diff=-10 (prefer A)
  [30,20]: diff=10 (prefer B)
  [400,50]: diff=350 (prefer B)
  [30,200]: diff=-170 (prefer A)

Sorted: [[30,200], [10,20], [30,20], [400,50]]
Send first 2 to A: 30+10=40
Send last 2 to B: 20+50=70
Total: 110 ✓

How to Choose the Right Criterion

Framework

Step 1: Identify what makes an element "better"

• Interval scheduling: Ends earlier → better
• Fractional knapsack: Higher value/weight ratio → better
• Two city scheduling: Larger cost difference → stronger preference

Step 2: Test with examples

• Create small test case
• Try different sorting criteria
• See which gives optimal result

Step 3: Verify

• Prove correctness (exchange argument, etc.)
• Or find counterexample if wrong

Decision Tree

What's the problem type?

Interval scheduling
  → Sort by END time

Matching/pairing
  → Sort both arrays by natural order

Optimization with ratio
  → Sort by ratio (value/weight, etc.)

Preference/difference
  → Sort by difference (costA - costB)

Custom greedy choice
  → Sort by greedy criterion

Common Wrong Criteria

1. Start Time (Interval Scheduling)

Problem: Maximum non-overlapping intervals

❌ Wrong: Sort by start time

intervals.sort(key=lambda x: x[0])

Why it fails: Can pick long interval that blocks many short ones.

✅ Correct: Sort by end time

intervals.sort(key=lambda x: x[1])

2. Value Only (Fractional Knapsack)

Problem: Maximize value in knapsack

❌ Wrong: Sort by value

items.sort(key=lambda x: x.value, reverse=True)

Why it fails: High-value item might be heavy (low value/weight ratio).

✅ Correct: Sort by value/weight ratio

items.sort(key=lambda x: x.value/x.weight, reverse=True)

3. Single Attribute (Two City Scheduling)

Problem: Minimize cost sending n to each city

❌ Wrong: Sort by costA

costs.sort(key=lambda x: x[0])

Why it fails: Doesn't consider relative preference.

✅ Correct: Sort by difference

costs.sort(key=lambda x: x[0] - x[1])

Debugging Checklist

When your greedy solution fails:

• Am I sorting by the right key?
• Should I sort ascending or descending?
• Should I sort by ratio instead of value?
• Should I sort by difference?
• Do I need to sort both arrays?
• Test with small example where wrong sort fails

Practice Problems

1. Non-overlapping Intervals (#435) - sort by end time
2. Two City Scheduling (#1029) - sort by difference
3. Fractional Knapsack - sort by ratio
4. Boats to Save People (#881) - sort both arrays

Conclusion

Choosing the right sorting criterion is critical for greedy correctness.

Key principles:

• Think about what makes an element "better"
• Test with examples
• Verify with proof or counterexample

For more on greedy sorting, see Greedy with Sorting Template and the complete greedy guide.