Problem Statement
Rescue Boat Dispatcher
You're a coast guard dispatcher coordinating a rescue operation. You need to determine the minimum number of boats required to rescue everyone.
You have an array people where people[i] represents the weight of the ith person, and each boat can carry a maximum weight of limit.
Each boat can carry at most 2 people at the same time, provided the sum of their weight is at most limit.
Return the minimum number of boats required to rescue everyone. It is guaranteed that each person can be carried by a boat.
Examples
Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: Only 1 boat is needed: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats are needed: 1 boat (1, 2), 1 boat (2), and 1 boat (3)
Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats are needed: 1 boat (3), 1 boat (3), 1 boat (4), and 1 boat (5)
Constraints
- 1 <= people.length <= 5 * 10^4
- 1 <= people[i] <= limit <= 3 * 10^4
Problem Breakdown
To solve this problem, we need to:
- Each boat can carry at most 2 people, so we need to optimize how we pair people
- Sorting the array helps us make optimal pairings
- Using a greedy approach, we can try to pair the heaviest person with the lightest person
- If the heaviest and lightest person can't fit in one boat, the heaviest person must take a boat alone
- The two-pointer technique is useful for efficiently pairing people from both ends of the sorted array
- The minimum number of boats is at least ceil(n/2) where n is the number of people
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Rescue Boat Dispatcher
You're a coast guard dispatcher coordinating a rescue operation. You need to determine the minimum number of boats required to rescue everyone.
You have an array people where people[i] represents the weight of the ith person, and each boat can carry a maximum weight of limit.
Each boat can carry at most 2 people at the same time, provided the sum of their weight is at most limit.
Return the minimum number of boats required to rescue everyone. It is guaranteed that each person can be carried by a boat.
Examples
Example 1:
Only 1 boat is needed: 1 boat (1, 2)
Example 2:
3 boats are needed: 1 boat (1, 2), 1 boat (2), and 1 boat (3)
Example 3:
4 boats are needed: 1 boat (3), 1 boat (3), 1 boat (4), and 1 boat (5)
Problem Breakdown
Constraints:
- 1 <= people.length <= 5 * 10^4
- 1 <= people[i] <= limit <= 3 * 10^4
Key Insights:
Each boat can carry at most 2 people, so we need to optimize how we pair people
Sorting the array helps us make optimal pairings
Using a greedy approach, we can try to pair the heaviest person with the lightest person
If the heaviest and lightest person can't fit in one boat, the heaviest person must take a boat alone
The two-pointer technique is useful for efficiently pairing people from both ends of the sorted array
The minimum number of boats is at least ceil(n/2) where n is the number of people
Real-World Application
This problem has several practical applications:
Rescue Operations
Optimizing resource allocation during emergency evacuations or rescue missions.
Transportation Logistics
Minimizing the number of vehicles needed to transport people or goods with weight constraints.
Resource Allocation
Efficiently allocating limited resources to meet various demands.
Scheduling Systems
Optimizing appointment scheduling when resources can handle at most two tasks simultaneously.