Maximum Total Importance of Roads - Solution & Explanation

Problem Overview: You have n cities connected by roads. Each city must be assigned a unique value from 1..n. The importance of a road equals the sum of the values of its two endpoints. The goal is to assign values so the total importance of all roads is maximized.

Approach 1: Two-Pointer Technique (O(n log n + m) time, O(n) space)

The key observation is that cities appearing in more roads contribute more times to the total importance. Start by computing the degree of each city (how many roads connect to it). Sort cities by degree. Now you want the largest labels assigned to the highest-degree cities. Using a two-pointer style assignment after sorting, place the smallest values at the start of the sorted list and the largest values at the end. Iterate through the roads and accumulate value[u] + value[v]. Degree counting takes O(m), sorting cities takes O(n log n), and the final accumulation is O(m). This approach uses a greedy strategy on a graph structure.

Approach 2: Sorting and Iteration (O(n log n + m) time, O(n) space)

This approach focuses directly on degrees and avoids storing explicit city-value mappings during assignment. First compute the degree of each city using a single pass over the roads. Sort the degree array in ascending order using sorting. Then assign values from 1 to n in sorted order and compute the contribution as degree[i] * assignedValue. Each city contributes its assigned value once per connected road, so multiplying by its degree accounts for all edges touching it. The final answer is the sum of these contributions. This greedy ordering guarantees that the most connected cities receive the largest labels.

Both approaches rely on the same greedy insight: maximize the contribution of frequently used nodes by giving them larger weights. A heap (priority queue) could also prioritize cities by degree, but sorting is simpler and equally efficient here.

Recommended for interviews: The sorting and iteration method is the expected solution. It demonstrates recognition of the greedy property: road contributions depend only on node degrees. Counting degrees and assigning labels after sorting shows strong algorithmic intuition and keeps the implementation short and clean.