Two City Scheduling

Schedule Interview of people in two different city, keeping travel cost minimum and there should be n/2 people in each city

Two City Scheduling

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.

Note: We are sorting on based on differences and not absolute differences so candidate with highest preference to city A will be negative and candidate with highest preference with city B will be positive

Code

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;
};