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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 int *cost1 = *(int **)a;
6 int *cost2 = *(int **)b;
7 return (cost1[0] - cost1[1]) - (cost2[0] - cost2[1]);
8}
9
10int twoCitySchedCost(int** costs, int costsSize, int* costsColSize) {
11 qsort(costs, costsSize, sizeof(int*), compare);
12 int totalCost = 0;
13 for (int i = 0; i < costsSize / 2; i++) {
14 totalCost += costs[i][0] + costs[i + costsSize / 2][1];
15 }
16 return totalCost;
17}In this solution, we first sort the list of costs based on the difference between the cost of city A and city B for each person. The comparison function is used with qsort. Then, we add the cost for city A for the first half of people and the cost for city B for the second half of people, returning the total minimized cost.