Maximum Total Importance of Roads

medium graph greedy sorting

Problem

There are n cities numbered 0 to n − 1 connected by bidirectional roads[i] = [a, b]. You must assign each city a distinct integer value from 1 to n. The importance of a road is the sum of the values of the two cities it connects. Return the maximum total importance over all roads achievable by an optimal assignment of values.

A city's value is counted once for every road touching it, so a city contributes value · degree to the total. To maximise the weighted sum we should pair the largest value with the largest degree: sort the cities by degree and hand out values 1…n in increasing order of degree, then sum value · degree.

Inputn = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]

Output43

Degrees are [2,3,4,2,1]. Assigning values 1..5 by ascending degree gives total 1·1 + 2·2 + 3·2 + 4·3 + 5·4 = 43.

roads (u,v; ...)

def maximum_importance(n, roads):
    degree = [0] * n
    for a, b in roads:
        degree[a] += 1
        degree[b] += 1
    degree.sort()
    total = 0
    for i in range(n):
        value = i + 1
        total += value * degree[i]
    return total

function maximumImportance(n, roads) {
  const degree = new Array(n).fill(0);
  for (const [a, b] of roads) {
    degree[a]++;
    degree[b]++;
  }
  degree.sort((x, y) => x - y);
  let total = 0;
  for (let i = 0; i < n; i++) {
    const value = i + 1;
    total += value * degree[i];
  }
  return total;
}

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] degree = new int[n];
        for (int[] r : roads) {
            degree[r[0]]++;
            degree[r[1]]++;
        }
        Arrays.sort(degree);
        long total = 0;
        for (int i = 0; i < n; i++) {
            long value = i + 1;
            total += value * degree[i];
        }
        return total;
    }
}

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> degree(n, 0);
        for (auto& r : roads) {
            degree[r[0]]++;
            degree[r[1]]++;
        }
        sort(degree.begin(), degree.end());
        long long total = 0;
        for (int i = 0; i < n; i++) {
            long long value = i + 1;
            total += value * degree[i];
        }
        return total;
    }
};

Explanation

Look at how often each city's value appears in the final sum. Summing road importances means adding up the two endpoint values of every road, so a city's value shows up exactly as many times as it has roads — its degree. The total is therefore Σ value(city) · degree(city).

We are free to assign the labels 1…n however we like, but we must use each exactly once. To make a weighted sum as large as possible with fixed weights (the degrees), the rearrangement inequality says to pair the biggest factor with the biggest weight: the city with the most roads should get the value n, the next-busiest gets n-1, and so on.

So the algorithm is short: count every city's degree by scanning the roads, sort the degrees ascending, then walk through them assigning value 1 to the smallest degree up to value n to the largest, accumulating value · degree.

We never actually need to know which physical city got which label — only the multiset of degrees matters for the total, which is why sorting the degree array alone is enough.

Worked example: degrees [2,3,4,2,1] sort to [1,2,2,3,4]. Multiplying by values 1,2,3,4,5 gives 1 + 4 + 6 + 12 + 20 = 43, the answer.

Time: O(E + V log V) Space: O(V)