Minimum Boats To Cross River

Easy
0/40
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
MicrosoftSalesforceSnapdeal Ltd.

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 5 
2 4 3 3
6 8
5 1 2 7 8 5
Sample Output 1:
3
4
Explanation For Sample Input 1:
For the first test case, 
If the person having weight 2 and one of the people having weight 3 goes in the same boat, while the other two persons cross the river using different boats. Then the total number of boats used will be 3, which is the minimum possible. Hence, the answer is 3 in this case.

For the second test case,
If the person having weight 2 and one of the person having weight 5 goes in the same boat and the persons having weight 1 and 7 goes in the same boat, while the other two persons cross the river using different boats. Then the total number of boats used will be 4, which is the minimum possible. Hence, the answer is 4 in this case.
Sample Input 2:
2
5 6
3 4 5 6 6 
6 3 
1 3 1 2 2 3
Sample Output 2:
5
4
Explanation For Sample Input 2:
For the first test case, 
No two or more can go on same boat. Hence, the answer is 5 in this case.

For the second test case,
If the person having weight 1 and one of the person having weight 2 goes in the same boat and the persons having weight 1 and 2 goes in the same boat, while the other two persons cross the river using different boats. Then the total number of boats used will be 4, which is the minimum possible. Hence, the answer is 4 in this case.
Hint

Among all the persons who have not been assigned a boat, check if the heaviest weight person can be paired with the least weight person.

Approaches (1)
Greedy Approach

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:

  1. Let N be the size of the array ARR.
  2. Sort the array ARR.
  3. 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.
  4. 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
  5. Return the variable MINBOATS.
Time Complexity

O(N*Log(N)), where N is the number of people.

 

It takes  O(N*Log(N)) time to sort the input array and the two-pointer approach takes O(N) time. Hence, the overall Time Complexity is O(N*Log(N)).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Boats To Cross River
Full screen
Console