package leetcode;

/**
 * https://leetcode.com/problems/boats-to-save-people/
 */
public class Problem881 {
    public int numRescueBoats(int[] people, int limit) {
        int count = 0;
        boolean[] visited = new boolean[people.length];
        for (int i = 0; i < people.length; i++) {
            if (visited[i]) {
                continue;
            }
            int l = limit - people[i];
            for (int j = i + 1; j < people.length; j++) {
                if (visited[j]) {
                    continue;
                }
                if (l - people[j] >= 0) {
                    l -= people[j];
                    visited[j] = true;
                    if (l == 0) {
                        break;
                    }
                }
            }
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Problem881 prob = new Problem881();
//        System.out.println(prob.numRescueBoats(new int[]{1, 2}, 3)); // 1
//        System.out.println(prob.numRescueBoats(new int[]{3, 2, 2, 1}, 3)); // 3
//        System.out.println(prob.numRescueBoats(new int[]{3, 5, 3, 4}, 5)); // 4
//        System.out.println(prob.numRescueBoats(new int[]{3, 5, 3, 4, 2}, 5)); // 4
//        System.out.println(prob.numRescueBoats(new int[]{3, 5, 3, 2, 4}, 5)); // 4
        System.out.println(prob.numRescueBoats(new int[]{21, 40, 16, 24, 30}, 50)); // 3
    }
}

@@ -12,16 +12,42 @@
 tcode;%0A%0A
+import java.util.Arrays;%0A%0A
 /**%0A * h
@@ -180,24 +180,53 @@
 nt limit) %7B%0A
+        Arrays.sort(people);%0A
         int 
@@ -428,17 +428,24 @@
     int 
-l
+newLimit
  = limit
@@ -458,16 +458,39 @@
 ple%5Bi%5D;%0A
+            int n = 1;%0A
         
@@ -509,19 +509,8 @@
  j =
- i + 1; j %3C
  peo
@@ -523,13 +523,24 @@
 ngth
-; j++
+ - 1; j %3E i; j--
 ) %7B%0A
@@ -641,17 +641,24 @@
     if (
-l
+newLimit
  - peopl
@@ -690,17 +690,49 @@
         
-l
+n++;%0A                    newLimit
  -= peop
@@ -801,18 +801,92 @@
     
-if (l == 0
+// The boat can only carry 2 people.%0A                    if (newLimit == 0 %7C%7C n == 2
 ) %7B%0A
@@ -987,24 +987,55 @@
    count++;%0A
+            visited%5Bi%5D = true;%0A
         %7D%0A  
@@ -1150,18 +1150,16 @@
 m881();%0A
-//
         
@@ -1224,18 +1224,16 @@
 ); // 1%0A
-//
         
@@ -1304,18 +1304,16 @@
 ); // 3%0A
-//
         
@@ -1376,34 +1376,32 @@
 , 4%7D, 5)); // 4%0A
-//
         System.o
@@ -1467,18 +1467,16 @@
 ); // 4%0A
-//
         
@@ -1635,20 +1635,177 @@
  50)); // 3%0A
+        System.out.println(prob.numRescueBoats(new int%5B%5D%7B%0A            2, 49, 10, 7, 11, 41, 47, 2, 22, 6, 13, 12, 33, 18, 10, 26, 2, 6, 50, 10%7D, 50)); // 11%0A
     %7D%0A%7D%0A

Update problem 881