Code Implementation
Rescue Boat Dispatcher Implementation
Below is the implementation of the rescue boat dispatcher:
123456789101112131415161718192021222324252627282930313233343536/** * Greedy Approach with Two Pointers * Time Complexity: O(n log n) - Dominated by the sorting operation * Space Complexity: O(1) - Constant extra space * * @param {number[]} people - Array of people's weights * @param {number} limit - Maximum weight each boat can carry * @return {number} - Minimum number of boats needed */function numRescueBoats(people, limit) { // Sort the array in ascending order people.sort((a, b) => a - b); // Initialize pointers and counter let i = 0; // lightest person let j = people.length - 1; // heaviest person let boats = 0; // Process all people while (i <= j) { // If lightest and heaviest can share a boat if (people[i] + people[j] <= limit) { i++; // Move to next lightest person } j--; // Move to next heaviest person boats++; // Count this boat } return boats;} // Test casesconsole.log(numRescueBoats([1, 2], 3)); // 1console.log(numRescueBoats([3, 2, 2, 1], 3)); // 3console.log(numRescueBoats([3, 5, 3, 4], 5)); // 4Step-by-Step Explanation
Let's break down the implementation:
- 1. Understand the Problem: First, understand that we need to find the minimum number of boats to rescue everyone, where each boat can carry at most 2 people and has a weight limit.
- 2. Sort the Array: Sort the array of people's weights in ascending order to facilitate the greedy approach.
- 3. Initialize Pointers: Set up two pointers: one at the beginning (lightest person) and one at the end (heaviest person).
- 4. Implement the Greedy Approach: Try to pair the lightest person with the heaviest person if their combined weight doesn't exceed the limit. Otherwise, the heaviest person takes a boat alone.
- 5. Count Boats: Increment the boat counter for each boat used, whether it carries one or two people.
- 6. Return the Result: Return the total number of boats needed to rescue everyone.
- 7. Test with Examples: Verify the solution with the provided examples and edge cases.
String Problems
Learning Objective
Implement the rescue boat dispatcher solution in different programming languages.
Rescue Boat Dispatcher Implementation
Below is the implementation of the rescue boat dispatcher in different programming languages. Select a language tab to view the corresponding code.
123456789101112131415161718192021222324252627282930313233343536/** * Greedy Approach with Two Pointers * Time Complexity: O(n log n) - Dominated by the sorting operation * Space Complexity: O(1) - Constant extra space * * @param {number[]} people - Array of people's weights * @param {number} limit - Maximum weight each boat can carry * @return {number} - Minimum number of boats needed */function numRescueBoats(people, limit) { // Sort the array in ascending order people.sort((a, b) => a - b); // Initialize pointers and counter let i = 0; // lightest person let j = people.length - 1; // heaviest person let boats = 0; // Process all people while (i <= j) { // If lightest and heaviest can share a boat if (people[i] + people[j] <= limit) { i++; // Move to next lightest person } j--; // Move to next heaviest person boats++; // Count this boat } return boats;} // Test casesconsole.log(numRescueBoats([1, 2], 3)); // 1console.log(numRescueBoats([3, 2, 2, 1], 3)); // 3console.log(numRescueBoats([3, 5, 3, 4], 5)); // 4Step-by-Step Explanation
11. Understand the Problem
First, understand that we need to find the minimum number of boats to rescue everyone, where each boat can carry at most 2 people and has a weight limit.
22. Sort the Array
Sort the array of people's weights in ascending order to facilitate the greedy approach.
33. Initialize Pointers
Set up two pointers: one at the beginning (lightest person) and one at the end (heaviest person).
44. Implement the Greedy Approach
Try to pair the lightest person with the heaviest person if their combined weight doesn't exceed the limit. Otherwise, the heaviest person takes a boat alone.
55. Count Boats
Increment the boat counter for each boat used, whether it carries one or two people.
66. Return the Result
Return the total number of boats needed to rescue everyone.
77. Test with Examples
Verify the solution with the provided examples and edge cases.
Language-Specific Notes
javascript
- JavaScript's sort() method sorts elements alphabetically by default, so we need to provide a comparison function for numeric sorting.
- The comparison function (a, b) => a - b sorts the array in ascending order.
- We use let for variables that will be modified during the algorithm.
python
- Python's sort() method sorts the list in-place in ascending order by default.
- We use += 1 for incrementing variables, which is equivalent to i++ in other languages.
- Python's class-based solution follows the LeetCode convention.
java
- Java requires explicit type declarations for all variables.
- Arrays.sort() is used to sort the array in ascending order.
- We create a main method to test the solution with the provided examples.
cpp
- C++ uses std::sort() from the
header to sort the vector. - We pass the vector by reference to avoid copying it.
- The main function demonstrates the solution with the provided examples.
Key Takeaways
- This problem demonstrates the effectiveness of the greedy approach for optimization problems.
- Sorting the array is a crucial step that enables the efficient pairing of people.
- The two-pointer technique is an elegant way to process elements from both ends of a sorted array.
- The key insight is to try to pair the heaviest person with the lightest person to minimize the number of boats.
- If the heaviest and lightest person can't fit in one boat, the heaviest person must take a boat alone.
- The time complexity is O(n log n) due to the sorting operation, which is acceptable for the given constraints.
- The space complexity is O(1), making this solution memory-efficient.
Try It Yourself
Modify the code to implement an alternative approach and test it with the same examples.
Challenge:
Implement a function that solves the rescue boat dispatcher problem using a different approach than shown above.
Common Edge Cases
All People Can Share Boats
If every pair of people (lightest with heaviest, second lightest with second heaviest, etc.) can share a boat, the minimum number of boats is n/2 (rounded up).
No People Can Share Boats
If no two people can share a boat (each person's weight is more than half the limit), each person needs their own boat.
Single Person
If there's only one person, we need exactly one boat.
Maximum Weight Equals Limit
If some people's weight equals the limit, they must take a boat alone.