**Physical Address**

304 North Cardinal St.

Dorchester Center, MA 02124

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] = [a`

denotes that there exists a _{i}, b_{i}]**bidirectional** road connecting cities `a`

and _{i}`b`

._{i}

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 * 10`

^{4}`1 <= roads.length <= 5 * 10`

^{4}`roads[i].length == 2`

`0 <= a`

_{i}, b_{i}<= n - 1`a`

_{i}!= b_{i}- There are no duplicate roads.

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

```
class Solution:
def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
Arr = [0] * n # i-th city has Arr[i] roads
for A,B in roads:
Arr[A] += 1 # Each road increase the road count
Arr[B] += 1
Arr.sort() # Cities with most road should receive the most score
summ = 0
for i in range(len(Arr)):
summ += Arr[i] * (i+1) # Multiply city roads with corresponding score
return summ
```

```
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<>();
for(int road[]:roads){
hm.put(road[0],hm.getOrDefault(road[0],0)+1);
hm.put(road[1],hm.getOrDefault(road[1],0)+1);
}
PriorityQueue<Pair> pq=new PriorityQueue<>();
for(int key:hm.keySet()){
pq.add(new Pair(key,hm.get(key)));
}
long ans=0;
while(pq.size()>0){
Pair pair=pq.remove();
map.put(pair.val,n);
n--;
}
for(int road[]:roads){
ans+=map.get(road[0]);
ans+=map.get(road[1]);
}
return ans;
}
}
```

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

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 >>**