aboutsummaryrefslogtreecommitdiff
path: root/other/max_total_importance_road.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/max_total_importance_road.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/max_total_importance_road.cpp')
-rw-r--r--other/max_total_importance_road.cpp34
1 files changed, 34 insertions, 0 deletions
diff --git a/other/max_total_importance_road.cpp b/other/max_total_importance_road.cpp
new file mode 100644
index 0000000..82380ab
--- /dev/null
+++ b/other/max_total_importance_road.cpp
@@ -0,0 +1,34 @@
+// 2285. Maximum Total Importance of Roads
+#include "leetcode.h"
+
+/*
+ * given an integer 'n' denoting the number of cities in a country. the cities
+ * are numbered from 0 to 'n - 1'. you are also given a 2d integer array 'roads'
+ * where 'roads{i} = {ai, bi}', where each value can only be used once. the
+ * importance of a road is then defined as the sum of the values of the two
+ * cities it connects. return the maximum total importance of all roads possible
+ * after assigning the values optimally.
+ */
+
+class Solution {
+public:
+ long long maximumImportance(int n, vector<vector<int>> &roads) {
+ long long cnt[50001] = {}, ans = 0;
+ for (auto &i : roads) {
+ ++cnt[i[0]];
+ ++cnt[i[1]];
+ }
+ sort(begin(cnt), begin(cnt) + n);
+ for (int i = 0; i < n; i++)
+ ans += cnt[i] * (i + 1);
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd r1 = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}};
+ vvd r2 = {{0, 3}, {2, 4}, {1, 3}};
+ printf("%lld\n", obj.maximumImportance(5, r1)); // expect: 43
+ printf("%lld\n", obj.maximumImportance(5, r2)); // expect: 20
+}