Two City Scheduling

Problem

Given 2n people and costs as [cost_a, cost_b], send exactly n people to city A and n to city B to minimize the total cost.

Sort by the difference cost_a - cost_b and send the first n people to A, since they are the cheapest to put in A relative to B, and the rest to B. Return 0 when there are no people.

Hint

The relative saving of sending someone to A instead of B is cost_a - cost_b.

Test cases

case 1

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

expected: 110

case 2

in: [[[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]]

expected: 1859

case 3

in: [[[1,2],[3,4]]]

expected: 5

case 4

in: [[[5,5],[5,5]]]

expected: 10

case 5

in: [[]]

expected: 0

Starter codePython

def two_city_scheduling(costs):
    # Your code here
    pass

5 test cases · run your code against them in the editor