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.

4 COMMENTS

LEAVE A REPLY