Minimum boxes required to carry all gifts

Given an array containing weights of gifts, and an integer representing maximum weight a box can contain. Each box carries at most 2 gifts at the same time, provided the sum of the weight of those gifts is at most limit of box. The task is to find the minimum number of boxes required to carry all gifts.

Note: It is guaranteed each gift can be carried by a box.

Examples:

Input: A = [4, 3, 2, 1], K = 4
Output: 3
Explanation:
4 boxes with weights (1, 3), (2), (3), and (4)

Input: A = [2, 5, 3, 4], K = 5
Output: 3
Explanation:
3 boxes with weights (2, 3), (4), and (5)

Approach:

Check if heavy gift fits with light one in a box.
If heavy gift can’t fit, it gets its box.
Pairing light and heavy gifts saves space efficiently.
Iterate from lightest to heaviest gifts, check if they fit in one box.
If total weight is less than K, put them in a box.

Below is the implementation of above approach:

// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;

// Function to return number of boxes
int numBoxes(int A[], int n, int K) {

    sort(A, A + n);

    int i = 0, j = n - 1;
    int ans = 0;

    while (i <= j) {
        ans++;
        if (A[i] + A[j] <= K)
            i++;
        j--;
    }

    return ans;
}

// Driver program
int main(){

    int A[] = {4, 3, 2, 1}, K = 4;

    int n=sizeof(A)/sizeof(A[0]);

    // Print required answer
    cout << numBoxes(A,n,K);

    return 0;
}

Output:

Time Complexity: O(nlogn), where n is the length of array.

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.