[LeetCode] 1029. Two City Scheduling - 문제풀이

Description

각 사람을 나타내는 배열에 0번째 요소는 a까지의 이동비용, 1번째 요소는 b까지의 이동 비용이라고 했을때 모든 사람이 a와 b에 절반씩 도착할 수 있는 최소 비용을 반환하는 문제입니다.

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

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

Example 1:

Input: costs = [[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.

Example 2:

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

Solution 1. Sorting, Greedy

public static int twoCitySchedCost(int[][] costs) {
    Arrays.sort(costs,(o1,o2)->{
        return (o1[1]-o1[0])-(o2[1]-o2[0]);
    });
    int cost = 0;
    int len = costs.length;

    for (int i = 0; i < len / 2; i++) {
        cost += costs[i][1] + costs[len-i-1][0];
    }
    return cost;
}

b로가는 비용과 a로 가는 비용의 차이가 제일 작은 순서대로 정렬해 주면 해당 사람을 A로 먼저 보내야 합니다. 이후 순회하며 시작과 끝사람을 각각 A,B로 가는 비용을 각 요소에서 계산하여 반환해줍니다.

0 = [840, 118] 1 = [448, 54] 2 = [926, 667] 3 = [577, 469] 4 = [184, 139] 5 = [259, 770]

Reference

Two City Scheduling - LeetCode