aboutsummaryrefslogtreecommitdiff
path: root/max_total_importance_road.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'max_total_importance_road.cpp')
-rw-r--r--max_total_importance_road.cpp34
1 files changed, 0 insertions, 34 deletions
diff --git a/max_total_importance_road.cpp b/max_total_importance_road.cpp
deleted file mode 100644
index 82380ab..0000000
--- a/max_total_importance_road.cpp
+++ /dev/null
@@ -1,34 +0,0 @@
-// 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
-}