Bird
Raised Fist0

Given the following code and input, what is the final returned total cost?

easy🧾 Code Trace Q12 of Q15
Greedy Algorithms - Two City Scheduling
Given the following code and input, what is the final returned total cost?
def twoCitySchedCost(costs):
    costs.sort(key=lambda x: 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

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))
A110
B150
C120
D140
Step-by-Step Solution
Solution:
  1. Step 1: Sort costs by difference cost[0] - cost[1]

    Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]
  2. Step 2: Assign first half to city A, rest to city B and sum costs

    First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sum matches manual calculation [OK]
Quick Trick: Sort by difference, assign first half to city A [OK]
Common Mistakes:
MISTAKES
  • Misordering after sorting by difference
  • Off-by-one in loop boundary
  • Adding wrong city cost for last half
Trap Explanation:
PITFALL
  • Confusing which half to assign to city A or B leads to wrong total cost.
Interviewer Note:
CONTEXT
  • Tests ability to trace sorting and assignment logic precisely.
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