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
- The total importance equals the sum over cities of
value(city) * degree(city). - This is a rearrangement problem: to maximise the sum of products, pair the largest values with the largest degrees.
- Compute each city's degree, then sort the degrees ascending.
- Assign values
1, 2, ..., nin that sorted order and sumdegree * 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.