LeetCode: Two City Scheduling

Posted on June 18, 2019July 26, 2020 by braindenny

Two City Scheduling

Similar Problems:

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 N people 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 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/two-city-scheduling
// Basic Ideas: greedy
//  Get the absolute difference for each person
//  Start to settle down with persons whos difference are bigger
// Complexity: Time O(n*log(n)), Space O(1)
import "sort"
func abs(v int) int {
    if v<0 { return -v }
    return v
}

func twoCitySchedCost(costs [][]int) int {
    sort.Slice(costs, func(i, j int) bool {
        return abs(costs[i][0]-costs[i][1]) > abs(costs[j][0]-costs[j][1])
    })

    N := len(costs)/2
    cityA, cityB := N, N
    res := 0
    for _, cost := range costs {
        if cityA == 0 {
            res += cost[1]
        } else if cityB == 0 {
            res += cost[0]
        } else {
            if cost[0] < cost[1] {
                res += cost[0]
                cityA--
            } else {
                res += cost[1]
                cityB--
            }
        }
    }
    return res
}

Post Views: 0