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<sub>i</sub>, b<sub>i</sub>] denotes that there exists a bidirectional road connecting cities a<sub>i</sub> and b<sub>i</sub>.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.
Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]Output: 43Explanation: The assigned values are [2,4,5,3,1].The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
Input: n = 5, roads = [[0,3],[2,4],[1,3]]Output: 20Explanation: The assigned values are [4,3,2,5,1].The total importance of all roads is 9 + 3 + 8 = 20.
class Solution: # Time: O(E + V log V) where E = len(roads), V = n # Space: O(V) def maximum_importance(self, n: int, roads: list[list[int]]) -> 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))
