Bird
Raised Fist0

Identify the bug in the following code snippet for Two City Scheduling:

medium🐞 Bug Identification Q14 of Q15
Greedy Algorithms - Two City Scheduling
Identify the bug in the following code snippet for Two City Scheduling:
def twoCitySchedCost(costs):
    costs.sort(key=lambda x: abs(x[0] - x[1]))
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total
ASorting by absolute difference instead of signed difference
BIncorrect calculation of n as half the length
CAdding cost[1] for the first half instead of cost[0]
DUsing enumerate instead of a simple for loop
Step-by-Step Solution
Solution:
  1. Step 1: Analyze sorting key

    The code sorts by absolute difference abs(cost[0] - cost[1]) instead of signed difference cost[0] - cost[1].
  2. Step 2: Effect of wrong sorting

    Sorting by absolute difference loses the direction of cost preference, causing suboptimal assignments and higher total cost.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Signed difference sorting is required for correct greedy assignment [OK]
Quick Trick: Sort by signed difference, not absolute [OK]
Common Mistakes:
MISTAKES
  • Sorting by absolute difference
  • Miscounting half the people
  • Swapping city costs in assignment
Trap Explanation:
PITFALL
  • Absolute difference sorting looks plausible but breaks the greedy logic by ignoring cost direction.
Interviewer Note:
CONTEXT
  • Tests attention to subtle sorting criteria critical for greedy correctness.
Master "Two City Scheduling" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes