1011. Capacity To Ship Packages Within D Days

• 1 <= weights[i] <= 500

O(nlogx), x is totalLoad (sum, our bs search range is form 1(or min value in weights) to sum)

do n times (isAbleToShipInDays), n is weights.length

```java
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = Integer.MAX_VALUE;
        int sum = 0;
        for (int w : weights) {
            left = Math.min(left, w);
            sum += w;
        }
        int right = sum;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (isAbleToShipInDays(mid, weights, days)) { // means cap can be smaller
                if (mid - 1 >= 0 && isAbleToShipInDays(mid-1, weights, days)) {
                    right = mid - 1;
                } else {
                    return mid;
                }
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    private boolean isAbleToShipInDays(int cap, int[] weights, int days) {
        System.out.println("cap:"+cap);
        int needDays = 1; // if can carry all weights -> 1 day
        int sum = 0;
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] > cap) {
                return false;
            }
            sum += weights[i];
            if (sum > cap) {
                needDays++; // 5
                sum = weights[i]; // 10
                // if (i == weights.length - 1) {
                //     needDays++;
                // }
            }
        }
        System.out.println("needDays:"+needDays);
        return needDays <= days;
    }
}

/**
[1,2,3,4, 5,   6,  7,  8,  9,10]
1. 3 6 10 15 21.   28. 36  45 55

11

[1,2,3,4,
56
7
8
9

 */
```