Example: Minimum Total Distance - rFronteddu/general_wiki GitHub Wiki

There are n distribution centers, all built along a straight line and they plan to build two warehouses to serve them. A distribution center has its demands met by the warehouse that is closest to it. Position the warehouses optimally, such that the sum of distances from the distribution centers to their closest warehouse is minimized.

Given an int array dist_centers, that represent the positions of the distribution centers, return the minimum sum of distances to their closest warehouses if the warehouses are positioned optimally.

Approach

Key Insights:

• Median: The median is the 'middle number' of a sorted array.
  • In 1D space, the median of a set of points minimizes the sum of absolute distances to those points. We can try to group the distribution centers into two clusters and place one warehouse in each cluster's median location.
• Minimizing Distance: We can look for the best split that minimizes the total distance.
• Note: The median minimizes the sum of absolute differences, even if you use just one of the two central elements. Approach:
• Sort the Distribution Centers: Sorting the distribution centers will help in partitioning them into two groups.
• Optimal Placement: For each possible split of the distribution centers into two groups, we place the first warehouse at the median of the first group and the second warehouse at the median of the second group.
• Calculate Total Distance: For each split, calculate the total distance and track the minimum.

For each possible split point:

• Calculate the median of the left group and the right group.
• Compute the total distance to the closest warehouse.
• Return the minimum sum of distances.

public class WarehousePlacement {
    public static int getMinTotalDistance(int[] dist_centers) {
        // Step 1: Sort the distribution centers
        Arrays.sort(dist_centers);
        int n = dist_centers.length;
        int minDistance = Integer.MAX_VALUE;

        // Step 2: Try every possible split point (i.e., from 1 to n-1)
        for (int split = 1; split < n; split++) {
            // Left group [0, split-1], Right group [split, n-1]

            // Step 3: Calculate the median for both groups
            int leftMedian = dist_centers[(split - 1) / 2];  // Median of left group
            int rightMedian = dist_centers[split + (n - split - 1) / 2]; // Median of right group

            // Step 4: Calculate the total distance to the nearest warehouse
            int totalDistance = 0;

            // Calculate distance for the left group to the left median
            for (int i = 0; i < split; i++) {
                totalDistance += Math.abs(dist_centers[i] - leftMedian);
            }

            // Calculate distance for the right group to the right median
            for (int i = split; i < n; i++) {
                totalDistance += Math.abs(dist_centers[i] - rightMedian);
            }

            // Update the minimum distance
            minDistance = Math.min(minDistance, totalDistance);
        }

        // Return the minimum distance found
        return minDistance;
    }
}