Capacity To Ship Packages Within D Days LeetCode solution in C++

1
class Solution {
2
 public:
3
  // function to check if it is possible to ship all the items within the given
4
  // number of days using a given weight capacity
5
  bool isPossible(int cp, vector<int> &weights, int days) {
6
    int d = 1;
7
    int cw = 0;
8
    // iterate through the weights and check if it is possible to ship all the
9
    // items
10
    for (auto x : weights) {
11
      if (x + cw <= cp) {
12
        // if the current weight can be added to the current capacity, add it
13
        cw += x;
14
      } else {
15
        // if not, increment the number of days required for shipping and start
16
        // a new shipment
17
        d++;
18
        cw = x;
19
        if (x > cp) {
20
          // if the current weight is greater than the current capacity, it is
21
          // impossible to ship all the items
22
          return false;
23
        }
24
      }
25
    }
26
    // check if it is possible to ship all the items within the given number of
27
    // days
28
    return d <= days;
29
  }
30

31
  // function to find the minimum weight capacity required to ship all the items
32
  // within the given number of days
33
  int shipWithinDays(vector<int> &weights, int days) {
34
    // initialize the search range for the weight capacity
35
    int s = 1;
36
    int e = 1E9;
37
    int ans = -1;
38

39
    // perform binary search on the weight capacity range
40
    while (s <= e) {
41
      // set the mid-point of the range as the current weight capacity
42
      int mid = (s + e) / 2;
43

44
      // check if it is possible to ship all the items within the given number
45
      // of days using the current weight capacity
46
      bool ok = isPossible(mid, weights, days);
47

48
      // if it is possible to ship all the items within the given number of days
49
      // using the current weight capacity, set the current weight capacity as
50
      // the new answer and reduce the upper bound of the weight capacity range
51
      if (ok) {
52
        ans = mid;
53
        e = mid - 1;
54
      } else {
55
        // if it is not possible to ship all the items within the given number
56
        // of days using the current weight capacity, increase the lower bound
57
        // of the weight capacity range
58
        s = mid + 1;
59
      }
60
    }
61

62
    // return the minimum weight capacity required to ship all the items within
63
    // the given number of days
64
    return ans;
65
  }
66
};