0881 Boats to Save People

0881 Boats to Save People.java

// O(nlogn) solution
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int l = 0, r = people.length - 1, res = 0;
        while (l <= r) {
            if (people[l] + people[r] <= limit) ++l;
            --r;
            ++res;
        }
        return res;
    }
}

/* Solution from leetcode sample 3 ms submission, time complexity O(n)
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int[] count = new int[limit+1];
        for(int p: people) {
            count[p]++;
        }
        int[] sorted = new int[people.length];
        int idx = people.length - 1;
        
        for(int i=limit; i>=1; i--) {
            for(int j=0; j<count[i]; j++) {
                sorted[idx--] = i;
            }
        }
        
        int boats = 0;
        int l = 0, r = people.length - 1;
        while (l <= r) {
            int leftNum = sorted[l];
            int rightNum = sorted[r];
            if (leftNum + rightNum <= limit) {
                l++;
            }
            r--;
            boats++;
        }
        
        return boats;
    }
}
*/