package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/boats-to-save-people/
 */
public class Problem881 {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int count = 0;
        boolean[] visited = new boolean[people.length];
        for (int i = 0; i < people.length; i++) {
            if (visited[i]) {
                continue;
            }
            int newLimit = limit - people[i];
            int n = 1;
            for (int j = people.length - 1; j > i; j--) {
                if (visited[j]) {
                    continue;
                }
                if (newLimit - people[j] >= 0) {
                    n++;
                    newLimit -= people[j];
                    visited[j] = true;
                    // The boat can only carry 2 people.
                    if (newLimit == 0 || n == 2) {
                        break;
                    }
                }
            }
            count++;
            visited[i] = true;
        }
        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
        System.out.println(prob.numRescueBoats(new int[]{
            2, 49, 10, 7, 11, 41, 47, 2, 22, 6, 13, 12, 33, 18, 10, 26, 2, 6, 50, 10}, 50)); // 11
    }
}

@@ -428,26 +428,51 @@
     int 
-newLimit =
+index = Arrays.binarySearch(people,
  limit -
@@ -481,16 +481,17 @@
 eople%5Bi%5D
+)
 ;%0A      
@@ -501,106 +501,103 @@
    i
-nt n = 1;%0A            for (int j = people.length - 1; j %3E i; j--) %7B%0A                if (visited%5Bj%5D
+f (index %3C 0) %7B%0A                index = -index - 1;%0A                if (index == visited.length
 ) %7B%0A
@@ -612,32 +612,31 @@
             
-continue
+index--
 ;%0A          
@@ -659,41 +659,126 @@
     
-    if (newLimit - people%5Bj%5D %3E= 0
+%7D else %7B%0A                int val = people%5Bindex%5D;%0A                while (index %3C people.length && val == people%5Bindex%5D
 ) %7B%0A
@@ -797,17 +797,21 @@
         
-n
+index
 ++;%0A    
@@ -824,36 +824,82 @@
     
+  %7D%0A
       
-newLimit -= people%5Bj%5D;
+          index--;%0A            %7D%0A            while (i %3C index) %7B
 %0A   
@@ -911,28 +911,29 @@
         
-    
+if (!
 visited%5B
 j%5D = tru
@@ -928,18 +928,17 @@
 ted%5B
-j%5D = true;
+index%5D) %7B
 %0A   
@@ -958,95 +958,102 @@
     
-// The boat can only carry 2 people.%0A                    if (newLimit == 0 %7C%7C n == 2) %7B
+if (limit - (people%5Bi%5D + people%5Bindex%5D) %3E= 0) %7B%0A                        visited%5Bindex%5D = true;
 %0A   
@@ -1112,32 +1112,57 @@
               %7D%0A
+                index--;%0A
             %7D%0A  
@@ -1184,39 +1184,8 @@
 ++;%0A
-            visited%5Bi%5D = true;%0A
     
@@ -1308,16 +1308,164 @@
 m881();%0A
+        System.out.println(prob.numRescueBoats(new int%5B%5D%7B2, 2%7D, 6)); // 1%0A        System.out.println(prob.numRescueBoats(new int%5B%5D%7B2, 4%7D, 5)); // 2%0A
         
@@ -2102,16 +2102,161 @@
 ; // 11%0A
+        System.out.println(prob.numRescueBoats(%0A            new int%5B%5D%7B3, 8, 4, 9, 2, 2, 7, 1, 6, 10, 6, 7, 1, 7, 7, 6, 4, 4, 10, 1%7D, 10)); // 11%0A
     %7D%0A%7D%0A

Update problem 881