Problem Statement:
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
Constraints
2 * n == costs.length2 <= costs.length <= 100costs.lengthis even.1 <= aCosti, bCosti <= 1000
Approach:
- For each person, calculate the
cost differencebetween going to city A and city B. - Sort people based on this difference, those who save more by going to city A come first.
- Send the
first halfof people to city A and the second half to city B. - Add up the total cost accordingly and
return the answer.
Time & Space Complexity:
Time Complexity: O(nlogn+n)=O(nlogn)
Space Complexity: O(n) Due to sort implementation
Dry Run
Input: costs = [[10,20],[30,200],[50,20],[30,20]]
Step 1: Sort the array Sorting rule = (b[1] - b[0]) - (a[1] - a[0]) → Calculate differences (cost to B - cost to A): [10,20] → 10 [30,200] → 170 [50,20] → -30 [30,20] → -10 costs = [[10,20],[30,200],[50,20],[30,20]] After sorting (descending order of difference): costs = [[30,200], [10,20], [30,20], [50,20]] Step 2: Initialize ans = 0 n = costs.length / 2 = 4 / 2 = 2 Step 3: Assign first n people to city A i = 0 → costs[0][0] = 30 → ans = 30 i = 1 → costs[1][0] = 10 → ans = 40 Step 4: Assign remaining people to city B i = 2 → costs[2][1] = 20 → ans = 60 i = 3 → costs[3][1] = 20 → ans = 80 Step 5: Return result ans = 80
Output: Result: 80
var twoCitySchedCost = function (costs) {
costs.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0]));
let ans = 0;
let n = costs.length / 2;
for (let i = 0; i < n; i++) {
ans += costs[i][0];
}
for (let i = n; i < 2 * n; i++) {
ans += costs[i][1];
}
return ans;
};
def twoCitySchedCost(costs):
# sort descending by (cost[1] - cost[0])
costs.sort(key=lambda x: x[1] - x[0], reverse=True)
n = len(costs) // 2
ans = sum(cost[0] for cost in costs[:n]) + sum(cost[1] for cost in costs[n:])
return ans
if __name__ == "__main__":
costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs)) # prints result
import java.util.Arrays;
import java.util.Comparator;
public class TwoCity {
public static int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator() {
public int compare(int[] a, int[] b) {
// sort descending by (cost[1] - cost[0])
return (b[1] - b[0]) - (a[1] - a[0]);
}
});
int n = costs.length / 2;
int ans = 0;
for (int i = 0; i < n; i++) ans += costs[i][0];
for (int i = n; i < costs.length; i++) ans += costs[i][1];
return ans;
}
public static void main(String[] args) {
int[][] costs = { {10,20}, {30,200}, {400,50}, {30,20} };
System.out.println(twoCitySchedCost(costs));
}
}
#include <bits/stdc++.h>
using namespace std;
int twoCitySchedCost(vector>& costs) {
int m = costs.size();
int n = m / 2;
// sort descending by (cost[1] - cost[0])
sort(costs.begin(), costs.end(), [](const vector& a, const vector& b) {
return (a[1] - a[0]) > (b[1] - b[0]);
});
int ans = 0;
for (int i = 0; i < n; ++i) ans += costs[i][0];
for (int i = n; i < m; ++i) ans += costs[i][1];
return ans;
}
int main() {
vector> costs = {{10,20},{30,200},{400,50},{30,20}};
cout << twoCitySchedCost(costs) << endl; // expected 110 (based on original logic)
return 0;
}
#include <stdio.h>
#include <stdlib.h>
typedef struct { int c0, c1; } Pair;
int cmp(const void *pa, const void *pb) {
const Pair *a = (const Pair*)pa;
const Pair *b = (const Pair*)pb;
int da = a->c1 - a->c0;
int db = b->c1 - b->c0;
// mimic JS comparator (b.diff - a.diff) -> sort descending by diff
return db - da;
}
int twoCitySchedCost(Pair *arr, int len) {
qsort(arr, len, sizeof(Pair), cmp);
int n = len / 2;
int ans = 0;
for (int i = 0; i < n; ++i) ans += arr[i].c0;
for (int i = n; i < len; ++i) ans += arr[i].c1;
return ans;
}
int main() {
Pair costs[] = {{10,20},{30,200},{400,50},{30,20}};
int len = sizeof(costs)/sizeof(costs[0]);
printf("%d\n", twoCitySchedCost(costs, len)); // prints result
return 0;
}
using System;
class Program {
static int TwoCitySchedCost(int[][] costs) {
Array.Sort(costs, (x, y) => (y[1] - y[0]) - (x[1] - x[0])); // descending by diff
int n = costs.Length / 2;
int ans = 0;
for (int i = 0; i < n; i++) ans += costs[i][0];
for (int i = n; i < costs.Length; i++) ans += costs[i][1];
return ans;
}
static void Main() {
int[][] costs = new int[][] {
new int[] {10, 20},
new int[] {30, 200},
new int[] {400, 50},
new int[] {30, 20}
};
Console.WriteLine(TwoCitySchedCost(costs)); // prints result
}
}
