Metro Land is a country located on a 2D Plane. They are having a summer festival for everyone in the country and would like to minimise the overall cost of travel for their citizens. Costs of travel are calculated as follows:
Determine the total cost of travel for all citizens to go to the festival at that location.
Complete Question
Approach
Repeat the coordinates in x points array and y points array according to the numsPoint array.
x1 = Take median of all the x axis points.
y1 = Take median of all the y axis points.
Solution
int cost(x, y, a, b) {
return (abs(x-a)+abs(y-b));
}
int greedy(vector<int> numpeople, vector<int> x, vector<int> y){
vector<int> xx, yy;
int ans = 0;
for(int i = 0 ; i < numpeople.size();i++){
int count = numpeople[i];
while(count--){
xx.push_back(x[i]);
yy.push_back(y[i]);
}
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
int mx, my;
mx = xx[xx.size() / 2];
my = yy[yy.size() / 2];
for(int i = 0; i < numpeople.size(); i++){
ans += numpeople[i] * cost(mx, my, x[i], y[i]);
}
return ans;
}
The solution is of O(n^2) time complexity.
I think the complexity is O(n*p) where n is the number of city and p is the max people in a city
I get your point but it can’t be less than O(nlogn) as sorting is included.
It should be median not average, please correct the same.
Yes. The code is correct. I have changed it to median in the theory.