Algocademy Logo

Minimum Number of Boats - Time Complexity: O(n log n) - JavaScript


You are given an array weights where weights[i] is the weight of the ith student, and an infinite number of boats where each boat can carry a maximum weight of maxWeight. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most maxWeight and the absolute difference of their weights shouldn't exceed maxDiff.

Return the minimum number of boats to carry every given student.

 

Example 1:

Input: weights = [2, 4, 2, 1], maxWeight = 6, maxDiff = 1
Output: 3
Explanation: 3 boats: (1, 2), (2) and (4)

Example 2:

Input: weights = [81, 37, 32, 88, 55, 93, 45, 72],
    maxWeight = 100, maxDiff = 10
Output: 6
Explanation: 6 boats (81), (37, 32), (88), (55, 45), (93), (72)

Understanding the Problem

The core challenge of this problem is to minimize the number of boats required to transport all students while adhering to the constraints of maximum weight and weight difference. This problem is significant in scenarios like evacuation planning, resource allocation, and logistics where optimizing the number of trips or resources is crucial.

Potential pitfalls include not considering the weight difference constraint or not pairing students optimally, leading to an increased number of boats.

Approach

To solve this problem, we need to think about pairing students in a way that maximizes the utilization of each boat. A naive solution would be to try every possible pair, but this would be computationally expensive. Instead, we can use a more efficient approach:

  1. Sort the array of weights.
  2. Use a two-pointer technique to try and pair the lightest and heaviest students that can share a boat.
  3. If they can share a boat, move both pointers inward; otherwise, move only the pointer for the heavier student.

This approach ensures that we are always trying to pair the heaviest possible student with the lightest possible student, which helps in minimizing the number of boats.

Algorithm

Here is a step-by-step breakdown of the algorithm:

  1. Sort the array of weights.
  2. Initialize two pointers: one at the start (lightest) and one at the end (heaviest) of the sorted array.
  3. Initialize a counter for the number of boats.
  4. While the start pointer is less than or equal to the end pointer:
    • Check if the current pair of students can share a boat based on the weight and weight difference constraints.
    • If they can share a boat, increment the start pointer and decrement the end pointer.
    • If they cannot share a boat, decrement only the end pointer.
    • Increment the boat counter in each iteration.
  5. Return the boat counter as the result.

Code Implementation

/**
 * @param {number[]} weights
 * @param {number} maxWeight
 * @param {number} maxDiff
 * @return {number}
 */
function minNumberOfBoats(weights, maxWeight, maxDiff) {
    // Sort the weights array
    weights.sort((a, b) => a - b);
    
    let start = 0;
    let end = weights.length - 1;
    let boats = 0;
    
    while (start <= end) {
        // Check if the lightest and heaviest can share a boat
        if (weights[start] + weights[end] <= maxWeight && Math.abs(weights[start] - weights[end]) <= maxDiff) {
            start++;
            end--;
        } else {
            end--;
        }
        boats++;
    }
    
    return boats;
}

// Example usage:
console.log(minNumberOfBoats([2, 4, 2, 1], 6, 1)); // Output: 3
console.log(minNumberOfBoats([81, 37, 32, 88, 55, 93, 45, 72], 100, 10)); // Output: 6

Complexity Analysis

The time complexity of this approach is O(n log n) due to the sorting step. The two-pointer traversal is O(n), making the overall complexity O(n log n). The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Potential edge cases include:

These cases are handled by the algorithm as it systematically checks each pair of students.

Testing

To test the solution comprehensively, consider the following test cases:

Using a testing framework like Jest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Conclusion

In this blog post, we discussed how to solve the problem of minimizing the number of boats required to transport students given weight and weight difference constraints. We explored a two-pointer approach that optimizes the solution and provided a detailed explanation and code implementation. Understanding and solving such problems is crucial for developing efficient algorithms and improving problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: