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[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;
}

Maximum Total Importance of Roads LeetCode Solution in Python

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

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<>();
        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;
    }
}

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