LeetCode Entry
2285. Maximum Total Importance of Roads
Sort graph by siblings and compute sum(i s)
2285. Maximum Total Importance of Roads medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/653
Problem TLDR
Sort graph by siblings and compute sum(i*s) #medium
Intuition
Notice that the more siblings the bigger rank should be to produce the optimal result.
Approach
We can sort the count array or use bucket sort of size n to reduce time complexity to O(n).
Complexity
-
Time complexity: \(nlog(n)\)
-
Space complexity: \(O(n)\)
Code
fun maximumImportance(n: Int, roads: Array<IntArray>): Long {
val counts = IntArray(n); var i = 1
for ((a, b) in roads) { counts[a]++; counts[b]++ }
return counts.sorted().sumOf { it * (i++).toLong() }
}
pub fn maximum_importance(n: i32, roads: Vec<Vec<i32>>) -> i64 {
let mut counts = vec![0; n as usize];
for r in roads { counts[r[0] as usize] += 1; counts[r[1] as usize] += 1}
counts.sort_unstable();
(0..n as usize).map(|i| counts[i] * (i + 1) as i64).sum()
}