2285. Maximum Total Importance of Roads LeetCode Solution

In this guide, you will get 2285. Maximum Total Importance of Roads LeetCode Solution with the best time and space complexity. The solution to Maximum Total Importance of Roads problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Total Importance of Roads solution in C++
Maximum Total Importance of Roads solution in Java
Maximum Total Importance of Roads solution in Python
Additional Resources

2285. Maximum Total Importance of Roads LeetCode Solution image

Problem Statement of Maximum Total Importance of Roads

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.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

2285. Maximum Total Importance of Roads LeetCode Solution in C++

class Solution {
 public:
  long long maximumImportance(int n, vector<vector<int>>& roads) {
    long ans = 0;
    vector<long> count(n);

    for (const vector<int>& road : roads) {
      const int u = road[0];
      const int v = road[1];
      ++count[u];
      ++count[v];
    }

    ranges::sort(count);

    for (int i = 0; i < n; ++i)
      ans += (i + 1) * count[i];

    return ans;
  }
};
/* code provided by PROGIEZ */

2285. Maximum Total Importance of Roads LeetCode Solution in Java

class Solution {
  public long maximumImportance(int n, int[][] roads) {
    long ans = 0;
    long[] count = new long[n];

    for (int[] road : roads) {
      final int u = road[0];
      final int v = road[1];
      ++count[u];
      ++count[v];
    }

    Arrays.sort(count);

    for (int i = 0; i < n; ++i)
      ans += (i + 1) * count[i];

    return ans;
  }
}
// code provided by PROGIEZ

2285. Maximum Total Importance of Roads LeetCode Solution in Python

class Solution:
  def maximumImportance(self, n: int, roads: list[list[int]]) -> int:
    count = [0] * n

    for u, v in roads:
      count[u] += 1
      count[v] += 1

    count.sort()
    return sum((i + 1) * c for i, c in enumerate(count))
 # code by PROGIEZ