From e27e913cedd5b017e19fa3de17d9a375800aff3a Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Wed, 22 Feb 2023 17:21:46 +0330 Subject: 1011 --- 1011/main.py | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100755 1011/main.py diff --git a/1011/main.py b/1011/main.py new file mode 100755 index 0000000..bec3d20 --- /dev/null +++ b/1011/main.py @@ -0,0 +1,36 @@ +#!/usr/bin/env python + +from typing import List + + +class Solution: + def shipWithinDays(self, weights: List[int], days: int) -> int: + start = max(weights) + end = sum(weights) + + def feasible(weights, c, days): + daysNeeded = 1 + currentLoad = 0 + for weight in weights: + currentLoad += weight + if currentLoad > c: + daysNeeded += 1 + currentLoad = weight + + return daysNeeded <= days + + while start < end: + mid = start + (end - start) // 2 + if feasible(weights, mid, days): + end = mid + else: + start = mid + 1 + + return start + + +if __name__ == "__main__": + solution = Solution() + print(solution.shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) + print(solution.shipWithinDays([3, 2, 2, 4, 1, 4], 3)) + print(solution.shipWithinDays([1, 2, 3, 1, 1], 4)) -- cgit v1.2.3