Algocademy Logo

Minimum Number of Boats in C++ (Time Complexity Analysis Included)


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 load balancing.

Potential pitfalls include not considering the weight difference constraint or not optimizing the pairing of students, leading to suboptimal solutions.

Approach

To solve this problem, we can use a greedy algorithm. The idea is to sort the weights and try to pair the lightest and heaviest students who can share a boat. This approach ensures that we use the fewest boats possible.

Naive Solution

A naive solution would involve checking all possible pairs of students, which is computationally expensive (O(n^2)) and not feasible for large inputs.

Optimized Solution

The optimized solution involves sorting the array and using a two-pointer technique to find the optimal pairs. This approach has a time complexity of O(n log n) due to sorting and O(n) for the two-pointer traversal, making it much more efficient.

Algorithm

  1. Sort the array of weights.
  2. Initialize two pointers: one at the beginning (lightest) and one at the end (heaviest) of the sorted array.
  3. Iterate through the array, trying to pair the lightest and heaviest students who can share a boat.
  4. If they can share a boat, move both pointers inward. Otherwise, move only the pointer at the end inward.
  5. Count the number of boats used.

Code Implementation


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minNumberOfBoats(vector<int>& weights, int maxWeight, int maxDiff) {
    // Sort the weights
    sort(weights.begin(), weights.end());
    
    int left = 0;
    int right = weights.size() - 1;
    int boats = 0;
    
    while (left <= right) {
        // Check if the lightest and heaviest can share a boat
        if (weights[left] + weights[right] <= maxWeight && abs(weights[left] - weights[right]) <= maxDiff) {
            left++;
            right--;
        } else {
            right--;
        }
        boats++;
    }
    
    return boats;
}

int main() {
    vector<int> weights1 = {2, 4, 2, 1};
    int maxWeight1 = 6;
    int maxDiff1 = 1;
    cout << "Minimum number of boats: " << minNumberOfBoats(weights1, maxWeight1, maxDiff1) << endl;

    vector<int> weights2 = {81, 37, 32, 88, 55, 93, 45, 72};
    int maxWeight2 = 100;
    int maxDiff2 = 10;
    cout << "Minimum number of boats: " << minNumberOfBoats(weights2, maxWeight2, maxDiff2) << endl;

    return 0;
}

Complexity Analysis

The time complexity of the optimized solution is O(n log n) due to the sorting step. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Potential edge cases include:

Each of these cases should be tested to ensure the algorithm handles them correctly.

Testing

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

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Conclusion

Understanding and solving problems like this one is crucial for developing strong problem-solving skills. The key is to think critically about the constraints and optimize the solution accordingly. Practice and exploration of similar problems can further enhance these skills.

Additional Resources

For further reading and practice, consider the following resources: