Problem of The Day: Maximum Total Importance of Roads

Problem Statement

Intuition

My first thought on solving this problem is to prioritize the nodes based on their degrees. The nodes with higher degrees should be assigned higher importance values because they are involved in more roads, thus contributing more to the overall importance when summed up.

Approach

1. I start by calculating the in-degree (number of roads connected) for each node using a dictionary.
2. Next, I use a max-heap to store the nodes sorted by their degrees in descending order.
3. I then assign the highest available importance value (starting from n and decreasing) to the nodes with the highest degrees.
4. Finally, I calculate the total importance by summing the importance values of the nodes for each road.

Complexity

• Time complexity: The time complexity of this solution is (O(E + n \log n)), where (E) is the number of edges (roads) and (n) is the number of nodes. The (O(E)) comes from calculating the in-degrees, and (O(n \log n)) comes from heap operations.
• Space complexity: The space complexity is (O(n)) due to the storage required for the dictionaries and heap.

Code

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        in_degree = defaultdict(int)
        node_map = defaultdict(int)
        for a, b in roads:
            in_degree[a] += 1
            in_degree[b] += 1

        max_heap = []
        for node, degree in in_degree.items():
            heappush(max_heap, [-degree, node])

        while max_heap:
            degree, node = heappop(max_heap)
            node_map[node] = n
            n -= 1

        res = 0
        for a, b in roads:
            res += node_map[a] + node_map[b]

        return res

EditoriaL

Approach: Sorting

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

        for edge in roads:
            degree[edge[0]] += 1
            degree[edge[1]] += 1

        degree.sort()

        value = 1
        total_importance = 0
        for d in degree:
            total_importance += value * d
            value += 1

        return total_importance