Sponsored
Sponsored
This approach relies on sorting the people by the difference between the cost of flying them to city A and city B. By doing so, we can initially assume that flying every person to city A is optimal, and then we adjust half of the people to go to city B based on minimal added cost.
The time complexity of this solution is O(n log n) due to the sorting step, and the space complexity is O(1) since we are sorting in place.
1import java.util.*;
2
3class Solution {
4 public int twoCitySchedCost(int[][] costs) {
5 Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
6 int n = costs.length / 2;
7 int totalCost = 0;
8 for (int i = 0; i < n; i++) {
9 totalCost += costs[i][0] + costs[i+n][1];
10 }
11 return totalCost;
12 }
13}The solution in Java utilizes the Arrays.sort() method with a custom comparator to sort by the difference in cost. Then, it calculates the total cost by sending the first half to city A and the second half to city B, adding their respective costs.