aboutsummaryrefslogtreecommitdiff
path: root/min_cost_connect_points.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_cost_connect_points.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_cost_connect_points.py')
-rw-r--r--min_cost_connect_points.py43
1 files changed, 43 insertions, 0 deletions
diff --git a/min_cost_connect_points.py b/min_cost_connect_points.py
new file mode 100644
index 0000000..d7c0b54
--- /dev/null
+++ b/min_cost_connect_points.py
@@ -0,0 +1,43 @@
+# 1584. Min Cost to Connect All Points
+from collections import defaultdict
+import heapq
+
+"""
+given a array 'points' representing integer coordinates of some points on a
+2d-plane, where 'points[i] = [x[i], y[i]]'. the cost of connecting two points
+'[x[i], y[i]]' and '[x[j], y[j]]' is the manhattan distance between them:
+'|x[i], - x[j]| + |y[i] + y[j]|', where '|val|' denotes the absolute value of
+'val'. return the minimum cost to make all points connected. all points are
+connected if there is exactly one simple path betwen any two points.
+"""
+
+
+class Solution(object):
+ def minCostConnectPoints(self, points):
+ manhattan = lambda p1, p2: abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
+ n, c = len(points), defaultdict(list)
+ for i in range(n):
+ for j in range(i + 1, n):
+ d = manhattan(points[i], points[j])
+ c[i].append((d, j))
+ c[j].append((d, i))
+ cnt, ans, vis, heap = 1, 0, [0] * n, c[0]
+ vis[0] = 1
+ heapq.heapify(heap)
+ while heap:
+ d, j = heapq.heappop(heap)
+ if not vis[j]:
+ vis[j], cnt, ans = 1, cnt + 1, ans + d
+ for record in c[j]:
+ heapq.heappush(heap, record)
+ if cnt >= n:
+ break
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]])
+ ) # expect: 20
+ print(obj.minCostConnectPoints([[3, 12], [-2, 5], [-4, 1]])) # expect: 18