Maximum Total Importance of Roads — LeetCode 2285 Python Solution

The problem

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

Example

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].

Python solution

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        deg = [0] * n
        for a, b in roads:
            deg[a] += 1
            deg[b] += 1
        deg.sort()
        return sum(i * v for i, v in enumerate(deg, 1))

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2285. Maximum Total Importance of Roads is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems