Greedy Algorithms: Optimal T-shirt Distribution

Problem Description

Imagine you’re organizing a community event where you need to distribute T-shirts to participants. Each person has a specific weight, and each T-shirt has a size. The challenge is to maximize the number of people who receive a properly fitting T-shirt while respecting certain constraints about size compatibility.

Problem Constraints

1. You have a list P of n people’s weights and a list S of m T-shirt sizes
2. Each T-shirt can stretch within a certain range defined by parameter t
3. A person with weight P[j] can wear a T-shirt of size S[i] if and only if: S[i] - t ≤ P[j] ≤ S[i] + t
4. Each person can receive at most one T-shirt
5. Each T-shirt can be given to at most one person

Example

Consider this scenario with 5 people and 5 T-shirt sizes, with a stretch factor t = 10:

Understanding the Solution

Why Greedy Works

This problem is perfectly suited for a greedy approach. Here’s why:

1. Optimal Substructure: Each assignment of a T-shirt to a person is independent of other assignments
2. Greedy Choice Property: Assigning each person the smallest possible fitting T-shirt leads to the optimal solution
3. Local Optimality: Making locally optimal choices (smallest fitting shirt) leads to a globally optimal solution

The Greedy Strategy

Our strategy can be broken down into these key steps:

1. Sort both people and T-shirts in ascending order
2. For each person (in order of increasing weight):
   • Find the smallest available T-shirt that fits them
   • Once found, mark that T-shirt as assigned
   • If no fitting T-shirt is found, move to the next person

Example Walkthrough

Let’s solve our example step by step:

1. First, sort both arrays:

   P (sorted): [40, 50, 70, 80, 84]
   S (sorted): [20, 32, 33, 45, 91]
   

2. For person with weight 40:

   • Try size 20: Too small (20-10 = 10 < 40)
   • Try size 32: Fits! (32-10 ≤ 40 ≤ 32+10)
   • Assign size 32 to this person

3. For person with weight 50:

   • Size 20: Too small
   • Size 32: Already assigned
   • Size 33: Too small
   • Size 45: Fits! (45-10 ≤ 50 ≤ 45+10)
   • Assign size 45 to this person

4. Continue this process…

The final result shows 3 people can get T-shirts:

• Weight 40 → Size 32
• Weight 50 → Size 45
• Weight 84 → Size 91

Solution Implementation

def maximize_tshirt_distribution(P, S, t):
    n = len(P)  # number of people
    m = len(S)  # number of T-shirts
    
    # Create sorted pairs of (weight, index) and (size, index)
    people = [(weight, i) for i, weight in enumerate(P)]
    shirts = [(size, i) for i, size in enumerate(S)]
    
    # Sort both arrays
    people.sort()
    shirts.sort()
    
    assigned = [False] * m  # Track which shirts are assigned
    matches = 0  # Count successful matches
    
    # Try to assign a shirt to each person
    for person_weight, person_idx in people:
        # Find smallest unassigned shirt that fits
        for j, (shirt_size, shirt_idx) in enumerate(shirts):
            if not assigned[j]:
                # Check if shirt fits within stretch interval
                if shirt_size - t <= person_weight <= shirt_size + t:
                    assigned[j] = True
                    matches += 1
                    break
    
    return matches

Complexity Analysis

Time Complexity

• Sorting both arrays: $O(n \log n + m \log m)$
• Main assignment loop: $O(n \cdot m)$ in worst case
• Overall: $O(n \log n + m \log m + n \cdot m)$

Space Complexity

• $O(n + m)$ for storing sorted arrays and assignment tracking

Why is this Solution Efficient?

1. Early Stopping

   • Once we find a fitting shirt for a person, we immediately move to the next person
   • This provides good average-case performance

2. Sorted Arrays

   • Sorting allows us to process people and shirts in a systematic order
   • Helps ensure we assign the smallest possible fitting shirt to each person

3. Simple Implementation

   • The algorithm is straightforward to implement and understand
   • No complex data structures required