Maximum Total Importance of Roads

Medium
466.

Maximum Total Importance of Roads

Maximum Total Importance of Roads is a medium coding problem on sorting, greedy and graph, asked in Amazon and Google interviews.

You are given n cities and a list of bidirectional roads. Assign each city a distinct integer value from 1 to n. A road's importance is the sum of the values of the two cities it joins.

Return the maximum total importance over all assignments.

Example 1

Input
n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output
43

Example 2

Input
n = 5, roads = [[0,3],[2,4],[1,3]]
Output
20

Example 3

Input
n = 2, roads = []
Output
0

Constraints

  • 2 <= n <= 40
  • 0 <= roads.length <= 60
  • There are no duplicate roads and no self-loops.
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var maximumImportance = function(n, roads) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Total Importance of Roads — Problem & Solution

Maximum Total Importance of Roads solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Total Importance of Roads is a medium coding problem on sorting, greedy and graph, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Sorting, Greedy, Graph, Heap
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given n cities and a list of bidirectional roads. Assign each city a distinct integer value from 1 to n. A road's importance is the sum of the values of the two cities it joins.

Return the maximum total importance over all assignments.

Example 1

Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43

Example 2

Input: n = 5, roads = [[0,3],[2,4],[1,3]]
Output: 20

Example 3

Input: n = 2, roads = []
Output: 0

Constraints

  • 2 <= n <= 40
  • 0 <= roads.length <= 60
  • There are no duplicate roads and no self-loops.
  • The answer fits in a signed 32-bit integer.

Hints for Maximum Total Importance of Roads

  1. Hint 1

    Rewrite the total as a sum over cities: each city contributes value * degree.

  2. Hint 2

    So the busiest city should get the largest value.

  3. Hint 3

    Sort the degrees ascending and pair them with the values 1, 2, …, n.

How to solve Maximum Total Importance of Roads

Rewrite the total as Σ value[city] · degree[city]; assign the largest values to the highest degrees by sorting degrees ascending and pairing with 1..n.

Approach

  1. Compute degrees.
  2. Sort ascending; sum degree[i] · (i + 1).

Why it works

Each city's value is counted once per incident road, so the total is a dot product of values and degrees, maximised by the rearrangement inequality when both are sorted the same way.

Complexity

  • Time — O(n log n + r)
  • Space — O(n)

Pitfalls

  • Use 64-bit arithmetic for the sum.

Reference solution

Python

def maximumImportance(n: int, roads) -> int:
    degree = [0] * n
    for a, b in roads:
        degree[a] += 1
        degree[b] += 1
    degree.sort()
    return sum(d * (i + 1) for i, d in enumerate(degree))

Java

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

C++

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

JavaScript

var maximumImportance = function(n, roads) {
    const degree = [];
    for (let i = 0; i < n; i++) degree.push(0);
    for (let i = 0; i < roads.length; i++) {
        degree[roads[i][0]]++;
        degree[roads[i][1]]++;
    }
    degree.sort(function(a, b) { return a - b; });
    let total = 0;
    for (let i = 0; i < n; i++) total += degree[i] * (i + 1);
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 274 sorting problems · the whole catalogue

Learn the technique: Sorting Algorithms · Greedy Algorithms