1011. Capacity To Ship Packages Within D Days

---

My Solution

The Key Idea for Solving This Coding Question

Use binary search to solve this coding question.

C++ Code 1

class Solution {
public:
    int shipWithinDays(vector<int> &weights, int days) {
        int left = 0, right = 0;
        for (int i = 0; i < weights.size(); ++i) {
            // The heighest capacity should be the total weight.
            right += weights[i];

            // The lowest capacity should be the maximum weight.
            if (left < weights[i]) {
                left = weights[i];
            }
        }

        while (left < right) {
            int middle = left + (right - left) / 2;
            if (isPossible(weights, days, middle)) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }

        if (isPossible(weights, days, left)) {
            return left;
        }
        return -1;;
    }

private:
    bool isPossible(vector<int> &weights, int days, int capacity) {
        int time = 1, load = 0;

        for (int i = 0; i < weights.size(); ++i) {
            if (load + weights[i] <= capacity) {
                load += weights[i];
            } else {
                load = weights[i];
                ++time;
            }
        }

        return time <= days;
    }
};

Time Complexity

$O(n+logn)$

$n$ is length of weights.

Space Complexity

$O(1)$

C++ Code 2

class Solution {
public:
    int shipWithinDays(vector<int> &weights, int day) {
        int left = 1, right = 25000000;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (!isPossible(weights, day, middle)) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        if (!isPossible(weights, day, left)) {
            ++left;
        }

        return left;
    }

private:
    bool isPossible(vector<int> &weights, int day, int load) {
        int time = 0, shipped = 0;
        for (auto &w : weights) {
            if (w > load) {
                // The weight of a single package (w) is greater
                // than teh capacity of the ship.
                return false;
            }

            if (shipped + w <= load) {
                shipped += w;
            } else {
                shipped = w;
                ++time;
                if (time > day) {
                    return false;
                }
            }
        }
        ++time;

        return time <= day;
    }
};

Time Complexity

$O(logn)$

$n$ is length of weights.

Space Complexity

$O(1)$

Miscellaneous