aboutsummaryrefslogtreecommitdiff
path: root/house_robber4.py
diff options
context:
space:
mode:
Diffstat (limited to 'house_robber4.py')
-rw-r--r--house_robber4.py45
1 files changed, 45 insertions, 0 deletions
diff --git a/house_robber4.py b/house_robber4.py
new file mode 100644
index 0000000..a8fb361
--- /dev/null
+++ b/house_robber4.py
@@ -0,0 +1,45 @@
+# 2560. House Robber IV
+
+"""
+there are several consecutive houses along a street, each of which has some
+money inside. there is also a robber, who wants to steal money from the
+homes, but he refuses to steal from adjacent homes. the capability of the
+robber is the maximum amount of money he steals from one house of all the
+houses he robbed. you are given an integer array 'nums' representing how much
+money is stahsed in each house. more formally, the i'th house from the left
+has 'nums[i]' dollars. you are also given an integer 'k', representing the
+minimum number of houses the robber will steal from. it is always possible to
+steal at least 'k' houses. return the minimum possible capability of the
+robber out of all the possible ways to steal at least 'k' houses.
+"""
+
+
+class Solution(object):
+ def minCapability(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ left, right = min(nums), max(nums)
+ while left < right:
+ mid = (left + right) // 2
+ prev, take = 0, False
+ for i in nums:
+ if prev:
+ prev = False
+ continue
+ if i <= mid:
+ take += 1
+ prev = True
+ if take >= k:
+ right = mid
+ else:
+ left = mid + 1
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCapability(nums=[2, 3, 5, 9], k=2))
+ print(obj.minCapability(nums=[2, 7, 9, 3, 1], k=2))