Sync LeetCode submission - Capacity To Ship Packages Within D Days (java)

thatbeautifuldream · thatbeautifuldream · commit 346b77ef8443 · 2021-09-02T18:30:33.000Z
diff --git a/practice/problems/capacity_to_ship_packages_within_d_days/solution.java b/practice/problems/capacity_to_ship_packages_within_d_days/solution.java
@@ -0,0 +1,39 @@
+class Solution {
+    public int shipWithinDays(int[] wt, int days) {
+        int max = 0;
+        int sum = 0;
+        for(int val : wt) {
+            sum += val;
+            max = Math.max(max, val);
+        }
+        if(wt.length == days) {
+            return max;
+        }
+        int low = max;
+        int high = sum;
+        int ans = 0;
+        while(low <= high) {
+            int mid = low + (high - low)/2;
+            if(isPossible(wt, mid, days) == true) {
+                ans = mid;
+                high = mid - 1;
+            }
+            else {
+                low = mid + 1;
+            }
+        }
+        return ans;
+    }
+    public static boolean isPossible(int[] wt, int mid, int days) {
+        int d = 1;
+        int sum = 0;
+        for(int i = 0; i<wt.length; i++) {
+            sum += wt[i];
+            if(sum > mid){
+                d++;
+                sum = wt[i];
+            }
+        }
+        return d<=days;
+    }
+}
