881. Boats to Save People

T: O(nlogn)
S: O(1)

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int count = 0;
        int total = 0;
        Arrays.sort(people);

        int n = people.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) { // 1,2,4,5 l=6       1,2,2,3. limit 3 // 2,3,7
            int sum = people[left] + people[right];

            if (sum <= limit) { // 3,3,4,5
                left++;
                right--;
                count++;
            } else {
                // people[left] + people[right] > limit, 
                // use right first (because it's sorted, so use right is more close to limit)
                // this also includes nums[right] == limit or nums[left] == limit, right at last will become left actually
                right--;
                count++;
            }
            if (left == right) { // when odd size, left == right, there is only one number left, so give it one count
                left++;
                right--;
                count++;
            }
        }
        return count;
    }
}


/**
T: O(nlogn)
S: O(1)

min boats to carray people

1 2

3


3 3 4 5

5

count++
left_limit = limit

        count = 1


        sum += curr // 3
        
        3,3,4,1        
5- 3 = 2 sum > left_limit
         count++
         sum = curr

         sum == 
         sum = 0

1 1 1 1


class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int count = 0;
        int total = 0;
        Arrays.sort(people);

        int n = people.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) { // 1,2,4,5 l=6       1,2,2,3. limit 3 // 2,3,7
            if (people[left] + people[right] >= limit) { // 3,3,4,5
                if ((people[left] + people[right]) == limit) {
                    left++;
                    right--;
                    count++;

                } else if ((people[left] + people[right]) > limit) {
                    if (people[left] == limit | people[right] == limit) { // this part will includes in right-- count++
                        if (people[right] == limit) {
                            right--;
                            count++;
                        }
                        if (people[left] == limit) {
                            left++;
                            count++;
                        }
                    } else { // // people[left] + people[right] > limit, use right first (because it's sorted, so use right is more close to limit)
                        right--;
                        count++;
                    }
                }
            } else {  // people[left] + people[right] < limit
                count++;
                left++;
                right--;
            }
            if (left == right) {
                count++;
                left++;
                right--;
            }
            
        }
        return count;
    }
}
 */