aboutsummaryrefslogtreecommitdiff
path: root/other/capacity_ship_d_day.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/capacity_ship_d_day.cpp')
-rw-r--r--other/capacity_ship_d_day.cpp50
1 files changed, 0 insertions, 50 deletions
diff --git a/other/capacity_ship_d_day.cpp b/other/capacity_ship_d_day.cpp
deleted file mode 100644
index 3612105..0000000
--- a/other/capacity_ship_d_day.cpp
+++ /dev/null
@@ -1,50 +0,0 @@
-// 1011. Capacity To Ship Packages Within D Days
-#include "leetcode.h"
-
-/*
- * a conveyor belt has packages that must be shipped from one port to another
- * within 'days' days. the i'th package on the conveyor belt has a weight of
- * 'weights[i]'. each day, the ship is loaded with packages on the conveyor belt
- * (in order given by 'weights'). we may not load more weight than the maximum
- * capacity of the ship. return the least weight capacity of the ship that will
- * result in all the packages on the conveyor belt being shipped within 'days'
- * days.
- */
-
-class Solution {
-public:
- int shipWithinDays(vector<int> &weights, int days) {
- auto r = accumulate(begin(weights), end(weights), 0);
- auto l = max(r / days, *max_element(begin(weights), end(weights)));
- while (l < r) {
- auto m = (l + r) / 2;
- if (countDays(weights, m) <= days)
- r = m;
- else
- l = m + 1;
- }
- return l;
- }
-
-private:
- int countDays(vector<int> &weights, int tot_cap, int cur_cap = 0,
- int res = 1) {
- for (auto w : weights) {
- cur_cap += w;
- if (cur_cap > tot_cap) {
- ++res;
- cur_cap = w;
- }
- }
- return res;
- }
-};
-
-int main() {
- Solution obj;
- vector<int> weights1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
- weights2 = {3, 2, 2, 4, 1, 4}, weights3 = {1, 2, 3, 1, 1};
- cout << obj.shipWithinDays(weights1, 5) << endl; // expect: 15
- cout << obj.shipWithinDays(weights2, 3) << endl; // expect: 6
- cout << obj.shipWithinDays(weights3, 4) << endl; // expect: 3
-}