โปรแกรมหาขนาดเครื่องบินขั้นต่ำสำหรับนักดำน้ำใน k วันใน Python

มีรายการ nums แทนกลุ่มคนดำน้ำ และ k วัน หาขนาดเครื่องบินขั้นต่ำที่รับได้ทุกกลุ่มใน k วัน (เรียงลำดับ, เครื่องบินบินวันละ 1 ครั้ง)

เช่น nums=[16,12,18,11,13], k=3 ให้ 28 จัดกลุ่ม [16,12], [18], [11,13]

ขั้นตอนการแก้ปัญหา

• Binary Search คำตอบระหว่าง max(nums) ถึง sum(nums)
• ตรวจสอบ mid: จำลองจัดกลุ่มวันละไม่เกิน mid นับวัน ใช้ได้กว่า k วัน -> เพิ่ม mid
• คืนค่า start

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums, k):
        if not nums: return 0
        start, end = max(nums), sum(nums)
        while start < end:
            mid = (start+end)//2
            days = 1; temp = 0
            for num in nums:
                if temp + num > mid:
                    days += 1; temp = num
                else:
                    temp += num
            if days > k: start = mid + 1
            else: end = mid
        return start

ob = Solution()
nums = [16,12,18,11,13]
k = 3
print(ob.solve(nums, k))

อินพุต

[16,12,18,11,13], 3

เอาต์พุต

28