Maximum total importance of roads

Greedy Graph Theory Sorting Heap (Priority Queue)

69.1% acceptance

Feb 25, 2026

1354

You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n. You are also given a 2D integer array roads where roads[i] = [ai, bi] indicates that there is a bidirectional road between nodes ai and bi. You need to assign each node a value from 1 to n, where each value is used exactly once. The importance of a road is then defined as the sum of the values of its two endpoints. Return the maximum total importance of all roads possible after assigning the values optimally.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_importance(n: i32, roads: Vec<Vec<i32>>) -> i64 {
    let n = n as usize;
    let mut degree = vec![0i64; n];
    for road in &roads {
      degree[road[0] as usize] += 1;
      degree[road[1] as usize] += 1;
    }
    degree.sort_unstable();
    let mut result = 0i64;
    for (i, &d) in degree.iter().enumerate() {
      result += d * (i as i64 + 1);
    }
    result
  }
}