LeetCode: Boats to Save People Solution

 The problem statement is copy pasted from leetcode as it is:

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)

 

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

My Solution:

package madwani.sushil.leetcode.Jan_8_15_2021;

import java.util.Arrays;

public class BoatsToSavePeople {
    public static void main(String[] args) {
        int[] people = new int[] {3,5,3,4}; // 4
        int[] people1 = new int[] {1,2}; // 1
        int[] people2 = new int[] {3,2,2,1}; // 3
        int[] people3 = new int[] {2,4}; // 2
        int[] people4 = new int[] {2,2}; // 1
        int[] people5 = new int[] {1,1,1}; // 2
        System.out.println(numRescueBoats(people, 5));
        System.out.println(numRescueBoats(people1, 3));
        System.out.println(numRescueBoats(people2, 3));
        System.out.println(numRescueBoats(people3, 5));
        System.out.println(numRescueBoats(people4, 6));
        System.out.println(numRescueBoats(people5, 3));
    }

    // Time Complexity : O(NLogN), Space Complexity : O(1)
    static int numRescueBoats(int[] people, int limit) {
        int numBoats = 0;
        // sort people based on weight
        Arrays.sort(people);
        int i = 0, j = people.length-1;
        while (i <=j) {
            numBoats++;
            // as max 2 people can be carried at time
            // it is always better to carry heaviest and lightest person at a time.
            if (people[i] + people[j] <= limit) {
                // if both can be carried, moved to the next lightest person
                i++;
            }
            // always heaviest person will be carried definitely so moved to the next heaviest person
            j--;
        }
        return numBoats;
    }
}