304 North Cardinal St.
Dorchester Center, MA 02124

# Maximum Total Importance of Roads LeetCode Solution

## Problem – Maximum Total Importance of Roads LeetCode Solution

You are given an integer `n` denoting the number of cities in a country. The cities are numbered from `0` to `n - 1`.

You are also given a 2D integer array `roads` where `roads[i] = [ai, bi]` denotes that there exists a bidirectional road connecting cities `ai` and `bi`.

You need to assign each city with an integer value from `1` to `n`, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.

Return the maximum total importance of all roads possible after assigning the values optimally.

Example 1:

``````Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43
Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.``````

Example 2:

``````Input: n = 5, roads = [[0,3],[2,4],[1,3]]
Output: 20
Explanation: The figure above shows the country and the assigned values of [4,3,2,5,1].
- The road (0,3) has an importance of 4 + 5 = 9.
- The road (2,4) has an importance of 2 + 1 = 3.
- The road (1,3) has an importance of 3 + 5 = 8.
The total importance of all roads is 9 + 3 + 8 = 20.
It can be shown that we cannot obtain a greater total importance than 20.
``````

Constraints:

• `2 <= n <= 5 * 104`
• `1 <= roads.length <= 5 * 104`
• `roads[i].length == 2`
• `0 <= ai, bi <= n - 1`
• `ai != bi`
• There are no duplicate roads.

### Maximum Total Importance of Roads LeetCode Solution in C++

``````long long maximumImportance(int n, vector<vector<int>>& roads) {
long long cnt = {}, res = 0;
for (auto &r : roads) {
++cnt[r];
++cnt[r];
}
sort(begin(cnt), begin(cnt) + n);
for (int i = 0; i < n; ++i)
res += cnt[i] * (i + 1);
return res;
}``````

### Maximum Total Importance of Roads LeetCode Solution in Python

``````class Solution:
def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
Arr =  * n  # i-th city has Arr[i] roads
Arr[B] += 1
summ = 0
for i in range(len(Arr)):
summ += Arr[i] * (i+1)  # Multiply city roads with corresponding score

return summ``````

### Maximum Total Importance of Roads LeetCode Solution in Java

``````class Solution {
class Pair implements Comparable<Pair>{
int val,freq;
Pair(int val,int freq){
this.val=val;
this.freq=freq;
}
public int compareTo(Pair o){
return o.freq-this.freq;
}
}
public long maximumImportance(int n, int[][] roads) {
HashMap<Integer,Integer> hm=new HashMap<>();
HashMap<Integer,Integer> map=new HashMap<>();
}
PriorityQueue<Pair> pq=new PriorityQueue<>();
for(int key:hm.keySet()){
}
long ans=0;
while(pq.size()>0){
Pair pair=pq.remove();
map.put(pair.val,n);
n--;
}
}
return ans;
}
}``````
##### Maximum Total Importance of Roads LeetCode Solution Review:

In our experience, we suggest you solve this Maximum Total Importance of Roads LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum Total Importance of Roads LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Maximum Total Importance of Roads LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions