Last Updated: 7 Apr, 2021
Minimum Boats To Cross River
Easy
Asked in companies
Ninja and his friends are on a trip. They have come across a river and want to cross the river with the help of boats. There are a total of 'N' people on the trip including Ninja himself. The weight of each person is given in an array 'ARR'. One boat can accommodate at most two persons only if the sum of their weight does not exceed 'L', i.e., the maximum weight capacity of the boat, otherwise, the boat will accommodate only one person. Given the weight of each person and the maximum weight capacity 'L', your task is to find the minimum number of boats required to ensure that everyone crosses the river.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and 'L', denoting the number of elements in the array 'ARR', and the maximum weight capacity of one boat respectively.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
Output Format:
For each test case, print a single integer - the minimum number of boats required.
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= L <= 10^9
1 <= N <= 10^5
1 <= ARR[i] <= L
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, 'L' denotes the maximum weight capacity of one boat, and 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.
Time Limit: 1 sec
Approaches
Approach: The idea is to observe the fact that it is always optimal to pair the heaviest weight person with the least weight person. If we want to send the heaviest weight person as a pair with some other person while crossing the river, then the weight of the heaviest weight person and his partner should not exceed the boat’s weight capacity. Therefore, pairing him with the least weight person gives us the best chance for his pairing. Note that, if the heaviest weight person can be paired with someone other than the person having the least weight, then the minimum number of boats required will remain the same.
Therefore, our approach will be to sort the input array and maintain two pointers, one at each end of the array. Now we will try to pair the current heaviest person and the person having the least weight. If the cumulative sum of their weights does not exceed the boat's capacity, we will pair them together using one boat and move both the pointers ahead. Otherwise, we will give one boat to the heaviest weight person and move the pointer pointing to the heaviest person ahead.
Algorithm:
- Let N be the size of the array ARR.
- Sort the array ARR.
- We will set the variable START as 0, the variable END as N - 1, and the variable MINBOATS as 0. START and END variables store the index of least weight and heaviest weight person from the remaining people. MINBOATS stores the minimum number of boats required.
- Iterate while START is less than equal to END,
- If the sum of ARR[START] and ARR[END] is less than or equal to L, then increment START by 1 and decrement END by 1. Here, we are checking if the heaviest weight can be paired with the least weight person.
- Otherwise, we will decrement END by 1.
- Increment MINBOATS by 1
- Return the variable MINBOATS.