Two City Scheduling

Similar Problems:

- LeetCode: Minimize Rounding Error to Meet Target
- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #greedy

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 }