aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_total_importance_road.c29
-rw-r--r--max_total_importance_road.cpp34
-rw-r--r--max_total_importance_road.py37
3 files changed, 90 insertions, 10 deletions
diff --git a/max_total_importance_road.c b/max_total_importance_road.c
index 145c3e2..55c9e07 100644
--- a/max_total_importance_road.c
+++ b/max_total_importance_road.c
@@ -1,12 +1,20 @@
// 2285. Maximum Total Importance of Roads
-#include <stdio.h>
-#include <stdlib.h>
+#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.
+ */
int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
long long maximumImportance(int n, int **roads, int roadsSize,
int *roadsColSize) {
- long long ans = 0, *timeShown = calloc(n, sizeof(long long));
+ long long ans = 0, *timeShown = (long long *)calloc(n, sizeof(long long));
for (int i = 0; i < roadsSize; i++)
for (int j = 0; j < 2; j++)
timeShown[roads[i][j]]++;
@@ -18,12 +26,13 @@ long long maximumImportance(int n, int **roads, int roadsSize,
}
int main() {
- int roads1[][2] = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}},
+ int r1[][2] = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}},
roadsColSize1[] = {6};
- int roads2[][2] = {{0, 3}, {2, 4}, {1, 3}}, roadsColSize2[] = {3};
- printf("%llu\n", maximumImportance(5, roads1, 6, roadsColSize1)); // expect:
- // 43
- printf("%llu\n", maximumImportance(5, roads1, 3, roadsColSize1)); // expect:
- // 20
- return 0;
+ int r2[][2] = {{0, 3}, {2, 4}, {1, 3}}, roadsColSize2[] = {3};
+ printf("%llu\n",
+ maximumImportance(5, (int **)r1, 6, roadsColSize1)); // expect:
+ // 43
+ printf("%llu\n",
+ maximumImportance(5, (int **)r1, 3, roadsColSize1)); // expect:
+ // 20
}
diff --git a/max_total_importance_road.cpp b/max_total_importance_road.cpp
new file mode 100644
index 0000000..327edb2
--- /dev/null
+++ b/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(int) r1 = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}};
+ vvd(int) 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
+}
diff --git a/max_total_importance_road.py b/max_total_importance_road.py
new file mode 100644
index 0000000..ae52cfe
--- /dev/null
+++ b/max_total_importance_road.py
@@ -0,0 +1,37 @@
+# 2285. Maximum Total Importance of Roads
+
+"""
+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(object):
+ def maximumImportance(self, n, roads):
+ """
+ :type n: int
+ :type roads: List[List[int]]
+ :rtype: int
+ """
+ sum, dp = 0, [0] * n
+ for i, j in roads:
+ dp[i] += 1
+ dp[j] += 1
+ roads.sort()
+ for i in range(len(roads)):
+ sum += dp[i] * (i + 1)
+ return sum
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maximumImportance(
+ n=5, roads=[[0, 1], [1, 2], [2, 3], [0, 2], [1, 3], [2, 4]]
+ )
+ )
+ print(obj.maximumImportance(n=5, roads=[[0, 3], [2, 4], [1, 3]]))