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 <= 400 <= roads.length <= 60There are no duplicate roads and no self-loops.The answer fits in a signed 32-bit integer.
Hints for Maximum Total Importance of Roads
Hint 1
Rewrite the total as a sum over cities: each city contributes
value * degree.Hint 2
So the busiest city should get the largest value.
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
- Compute degrees.
- 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