Problem Overview

A company is planning to interview 2n people. You must send exactly n people to city A and the remaining n people to city B.

The cost of sending each person to either city A or city B is given as a 2D array costs, where:

• costs[i][0] is the cost of sending the i-th person to city A.
• costs[i][1] is the cost of sending the i-th person to city B.

Your task is to minimize the total cost of sending exactly n people to each city.

Example 1

Input: costs = [[10,20],[30,200],[50,50],[30,20]]
Output: 110
Explanation:
Send person 1 → city A (cost 10)
Send person 2 → city A (cost 30)
Send person 3 → city B (cost 50)
Send person 4 → city B (cost 20)
Total cost = 10 + 30 + 50 + 20 = 110

Example 2

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

---

Intuition / Approach

We need to decide who should go to city A and who should go to city B such that:

1. Exactly n people go to each city.
2. The total cost is minimized.

A greedy approach works perfectly for this problem.

Step 1: Start with everyone going to one city

Let’s initially assume everyone goes to city A.
The total cost will be the sum of all costs[i][0].

Step 2: Calculate the “extra cost” (difference)

For each person i, if we instead send them to city B, the additional cost (or savings) will be:

difference = costs[i][1] - costs[i][0]

• If this difference is negative, sending them to city B is cheaper.
• If this difference is positive, sending them to city A is cheaper.

Step 3: Choose the n smallest differences

Since we need n people in city B, we sort all people by their cost difference.
Then we send the first n people (with the smallest differences) to city B.

This ensures the total cost is minimized, as we choose the most cost-effective switches from A → B.

---

Algorithm Explanation

1. Initialize totalCost = 0.
2. Compute the cost difference for each person:
   • diff[i] = costs[i][1] - costs[i][0].
3. Sort the array based on these differences.
   • People with the smallest difference (cheaper to send to city B) come first.
4. Select the first n people for city B and the rest for city A.
5. Add up their respective costs and return the total.

---

Java Code Implementation

import java.util.Arrays;

public class TwoCityScheduling {

    public int twoCitySchedCost(int[][] costs) {
        // Sort by the difference between cost to city B and cost to city A
        Arrays.sort(costs, (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));

        int n = costs.length / 2;
        int totalCost = 0;

        // First n people go to city B (smaller differences)
        // Remaining n people go to city A
        for (int i = 0; i < costs.length; i++) {
            if (i < n) {
                totalCost += costs[i][1]; // send to city B
            } else {
                totalCost += costs[i][0]; // send to city A
            }
        }

        return totalCost;
    }

    public static void main(String[] args) {
        TwoCityScheduling solver = new TwoCityScheduling();

        int[][] costs1 = {{10, 20}, {30, 200}, {50, 50}, {30, 20}};
        System.out.println(solver.twoCitySchedCost(costs1)); // Output: 110

        int[][] costs2 = {{259,770},{448,54},{926,667},{184,139},{840,118},{577,469}};
        System.out.println(solver.twoCitySchedCost(costs2)); // Output: 1859
    }
}

---

Step-by-Step Example

Let’s walk through the example [[10,20],[30,200],[50,50],[30,20]].

Person	City A	City B	Diff (B – A)
1	10	20	+10
2	30	200	+170
3	50	50	0
4	30	20	-10

Sort by difference:
[-10, 0, +10, +170]

• First two (smallest differences): send to City B.
  • Person 4 → City B (20)
  • Person 3 → City B (50)
• Remaining two: send to City A.
  • Person 1 → City A (10)
  • Person 2 → City A (30)

Total = 20 + 50 + 10 + 30 = 110

---

Complexity Analysis

1. Time Complexity:O(n log n)
   • Sorting the array based on cost differences dominates the time complexity.
   • The rest of the operations are linear (O(n)).
2. Space Complexity:O(1)
   • Sorting is done in place, and only a few variables are used.
   • Hence, constant extra space.

---

Alternative Approach (Without Sorting)

If performance is a concern and sorting seems expensive for large input, you can use a priority queue (min-heap) or partial sorting (nth_element) to find the smallest n differences.

However, since sorting is efficient and simple to implement in Java, the greedy sort-based approach is generally preferred.

---

Why This Greedy Strategy Works

The reason this greedy approach is optimal is that each person’s relative cost difference between the two cities is independent of others.
By sorting by these differences and choosing the lowest n for city B, we guarantee that we pick the globally minimal configuration of total cost.

This problem is essentially a pairwise optimization problem — minimizing the sum of two subsets under a balancing constraint (n people in each city).