⚡Flashcard Drill➔
NeetCode #789LC-2285MediumGreedy
← Back to All Problems

#789 · #2285 · Maximum Total Importance of Roads(道路的最大总重要性)

📌 Problem Statement & Constraints

You are given an integer n (cities numbered 0..n-1) and roads where roads[i] = [a, b] is a bidirectional road. Assign each city a unique value from 1 to n; the importance of a road is the sum of its two cities' values, and the total importance is the sum over all roads. Return the maximum total importance. Constraints: 2 <= n <= 5 * 10^4, 1 <= roads.length <= 5 * 10^4, 0 <= a, b < n.

💡 Core Algorithmic Approaches

  1. The total importance equals the sum over cities of value(city) * degree(city).
  2. This is a rearrangement problem: to maximise the sum of products, pair the largest values with the largest degrees.
  3. Compute each city's degree, then sort the degrees ascending.
  4. Assign values 1, 2, ..., n in that sorted order and sum degree * value.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumImportance(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))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n + m): sorting the degrees plus scanning the roads.
💾 Space Complexity
O(n): the degree array.

⚠️ Interview Pitfalls & Follow-ups

  • Assigning values by city index: the assignment must follow the degrees, not the numbering.
  • Forgetting that both endpoints gain a degree per road: each road increments two cities.
  • Sorting descending and assigning n - i: equivalent, but mixing the two directions causes errors.
  • Using the number of distinct neighbours instead of the degree: parallel roads count multiple times.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems