Maximum Total Importance of Roads

MediumGreedyGraphSortingHeap (Priority Queue)

Solution

export function maximumImportance(n: number, roads: number[][]): number {
  const degrees = new Array(n).fill(0);
  for (const [a, b] of roads) {
    degrees[a] += 1;
    degrees[b] += 1;
  }
 
  return degrees.sort((a, b) => a - b).reduce((acc, degree, i) => acc + degree * (i + 1), 0);
}

Complexity

  • Time: O(n * logn)
  • Space: O(n)