There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly Npeople arrive in each city.

 

Example 1:

Input:

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

Output:

110

Explanation:

The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

 

Note:

1. 1 <= costs.length <= 100
2. It is guaranteed that costs.length is even.
3. 1 <= costs[i][0], costs[i][1] <= 1000

 

class Solution {

    /**
     * @param Integer[][] $costs
     * @return Integer
     */
    function twoCitySchedCost($costs) {
        usort($costs, function($arr1, $arr2) {
            return (abs($arr1[1]-$arr1[0]) < abs($arr2[1]-$arr2[0]) ) ? 1 : -1;
        });

        $a = 0;
        $b = 0;
        $total = 0;
        foreach($costs as $c){
            if($c[0] < $c[1]){

                if($a < count($costs)/2){
                    $total += $c[0];
                    $a ++;
                } else {
                    $total += $c[1];
                    $b ++;
                }
               
            } else{
                if($b < count($costs)/2){
                    $total += $c[1];
                    $b ++;
                } else {
                    $total += $c[0];
                    $a ++;
                }
                
            } 
        } 

        return $total;
    }
}

16ms.

 

 

Thoughts:

• This code was used for the contest, so it’s not well structured (in terms of redundancy)
• The basic idea:
  • Sort by switching cost (price diff), DESC.
  • then for each person, assign to lower cost city until full.
    • in case of full, assign to city with higher cost
  • Since sorted by price diff, at the time one city is full,  the cost to switch remaining people to the second choice is the lowest

If I’m a interviewer:

• Let’s try three cities….
• What about the capacity of each city is specified?
• And what about the capacity is flexible and within a range provided?