Two City Scheduling

A company is planning to interview 2n people. You are given an array, costs, where costs[i] = [aCosti, bCosti]: aCosti is the cost of flying the ith person to city A. bCosti is the cost of flying the ith person to city B. Return the minimum total cost to fly everyone to a city, such that exactly n people end up in each city.

Problem Statement

A company is planning to interview 2n people. You are given an array, costs, where costs[i] = [aCosti, bCosti]:

• aCosti is the cost of flying the ith person to city A.
• bCosti is the cost of flying the ith person to city B.

Return the minimum total cost to fly everyone to a city, such that exactly n people end up in each city.

Examples

Example 1

Input: costs = [[10,20],[30,200],[400,50],[30,20]]

Output: 110

Explanation:

• Person 1 goes to city A for 10.
• Person 2 goes to city A for 30.
• Person 3 goes to city B for 50.
• Person 4 goes to city B for 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110, with half the people going to 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

Constraints

• 2 * n == costs.length
• 2 ≤ costs.length ≤ 100
• costs.length is even.
• 1 ≤ aCosti, bCosti ≤ 1000

Solution

The key idea: we sort people by the difference between their two costs (aCost - bCost). This tells us how much cheaper (or more expensive) it is to send someone to city A compared to city B.

Why This Works

• If a person's aCost - bCost is very negative, city A is much cheaper for them, so they should go to city A.
• If a person's aCost - bCost is very positive, city B is much cheaper for them, so they should go to city B.
• By sorting everyone based on this difference, the people who benefit most from going to city A end up at the start of the sorted list, and the people who benefit most from going to city B end up at the end.

Steps

• We sort costs based on (aCost - bCost), from smallest to largest.
• We use two pointers: start, beginning at the front of the sorted list, and end, beginning at the back.
• We move both pointers toward the middle, one step at a time:
  • We send the person at start to city A, adding their aCost to our total.
  • We send the person at end to city B, adding their bCost to our total.
• Since the array has 2n people, this loop runs exactly n times, sending n people to city A and n people to city B — exactly the split we need.
• The final totalCost is our answer.

Code

/**
 * @param {number[][]} costs
 * @return {number}
 */
var twoCitySchedCost = function (costs) {
    costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));

    let totalCost = 0;
    let start = 0;
    let end = costs.length - 1;

    while (start < end) {
        totalCost += costs[start][0] + costs[end][1];

        start++;
        end--;
    }
    return totalCost;
};