aboutsummaryrefslogtreecommitdiff
path: root/marbles_in_bags.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-30 21:18:18 -0600
committerJack Sangdahl <[email protected]>2025-03-30 21:18:18 -0600
commit62ec80fb2041268d4d7aaad4cbe5b3fc7c67ce3f (patch)
treea4c81d970922e8cf01e16819f943391d4d12d88e /marbles_in_bags.py
parente98eec899e88073264dff288b0778f9e675ecb2e (diff)
downloadleetcode-62ec80fb2041268d4d7aaad4cbe5b3fc7c67ce3f.tar.gz
leetcode-62ec80fb2041268d4d7aaad4cbe5b3fc7c67ce3f.zip
2551. put marbles in bags
Diffstat (limited to 'marbles_in_bags.py')
-rw-r--r--marbles_in_bags.py33
1 files changed, 33 insertions, 0 deletions
diff --git a/marbles_in_bags.py b/marbles_in_bags.py
new file mode 100644
index 0000000..0cb520c
--- /dev/null
+++ b/marbles_in_bags.py
@@ -0,0 +1,33 @@
+# 2551. Put Marbles in Bags
+
+"""
+you have 'k' bags. you are given a 0-indexed integer array 'weights' where
+'weights[i]' is the weight of the i'th marble. you are also given the integer
+'k'. divide the marbles into the 'k' bags according to the following rules
+- no bag is empty
+- if the i'th marble and the j'th marble are in a bag, then all the marbles
+with an index between the i'th and j'th indices should also be in that same
+bag.
+- if a bag onsists of all the marbles with an index from 'i' to 'j'
+inclusively, then the cost of the bag is 'weights[i] + weights[j]' the score
+after distributing the marbles is the sum of the costs of all the 'k' bags.
+return the difference between the maximum and minimum scores among marble
+distributions
+"""
+
+
+class Solution(object):
+ def putMarbles(self, weights, k):
+ """
+ :type weights: List[int]
+ :type k: int
+ :rtype: int
+ """
+ pairs = sorted([weights[i] + weights[i + 1] for i in range(len(weights) - 1)])
+ return sum(pairs[len(pairs) - k + 1 :]) - sum(pairs[: k - 1])
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.putMarbles(weights=[1, 3, 5, 1], k=2))
+ print(obj.putMarbles(weights=[1, 3], k=2))