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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int twoCitySchedCost(vector<vector<int>>& costs) {
7 sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
8 return (a[0] - a[1]) < (b[0] - b[1]);
9 });
10 int n = costs.size() / 2;
11 int totalCost = 0;
12 for (int i = 0; i < n; ++i) {
13 totalCost += costs[i][0] + costs[i + n][1];
14 }
15 return totalCost;
16}Similar to the C solution, the costs are sorted by profit of sending each person to city A over city B. After sorting, the first half are sent to city A and the second half to city B, minimizing the overall cost.