Dig into optimization problems with greedy algorithms through practical scenarios and solutions.

Coding

Makes locally optimal choices at each step, aiming for a globally optimal solution in problem-solving scenarios, often without reassessment.

Greedy Techniques

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# Statement
A big ship with numerous passengers is sinking, and there is a need to evacuate these people with the minimum number of life-saving boats. Each boat can carry, at most, two persons however, the weight of the people cannot exceed the carrying weight limit of the boat.

We are given an array, `people`, where `people[i]` is the weight of the $i^{th}$ person, and an infinite number of boats, where each boat can carry a maximum weight, `limit`. Each boat carries, at most, two people at the same time. This is provided that the sum of the weight of these people is under or equal to the weight limit.

You need to return the minimum number of boats to carry all persons in the array.

**Constraints:**

- $1 \leq$ `people.length` $\leq 5 \times 10^3$

- $1 \leq$ `people[i]` $\leq$ `limit` $\leq 3 \times 10^3$
# Solution
You may have already, brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and implementation constraints.
## Naive approach
The naive approach is to use a nested loop. For each person, we can check all the remaining people to see if they can form a pair that fits into a boat. If we find a pair, we’ll remove them from the array, increment the number of boats used, and move to the next person. If we can't find a pair for a person, we put them in a boat alone and increment the number of boats used. We repeat this process until all people are rescued. 



The time complexity of this approach is $O(n^2)$, since we’ll use the nested loop to make pairs.
## Optimized approach using the Greedy pattern
To solve the problem, we can use the greedy pattern and pair people with the lightest and heaviest people available, as long as their combined weight does not exceed the weight limit. If the combined weight exceeds the limit, we can only send one person on that boat. This approach ensures that we use the minimum number of boats to rescue the people.

The steps to implement the approach above are given below:

1) Sort the `people` array in ascending order so that the lightest person is at the start of the array, and the heaviest person is at the end.

2) Initialize two pointers, `left` and `right`. The `left` pointer points to the lightest person at the start of the array, and the `right` pointer points to the heaviest person at the end of the array. Next, a variable, `boats`, is initialized to `0`, representing the number of boats used.
3) Iterate over the `people` array until the `left` pointer is greater than the `right` pointer. This means that all people have been rescued. Perform the following steps in each iteration of the loop 
   

   - Check if both the lightest and heaviest persons can fit in one boat, i.e., `people[left] + people[right]` is less than or equal to `limit`. If they can fit, the `left` pointer is incremented and the `right` pointer is decremented.

   - If they cannot fit in one boat, the heaviest person is rescued alone, and the `right` pointer is decremented.

   - The `boats` variable is incremented by `1`, representing the number of boats used.

4) Return the minimum number of boats required to rescue all the people.



Let's solve the Boats to Save People problem using the Greedy pattern.

Solution: Boats to Save People

Statement▼

Solution: Boats to Save People

Statement▼