Property Booking Optimizer

Given:

• A list of properties where each property has (id, neighborhood, capacity)
• A group size (number of people that need accommodation)
• A target neighborhood

Goal:
Find the optimal combination of properties in the given neighborhood that can accommodate the group with these rules:

1. Total capacity must be >= group size
2. Choose the combination with minimum total capacity that exceeds group size
3. If multiple combinations have same capacity, choose the one with fewer properties
4. If no valid combination exists, return empty list

Examples:

Example 1:
Properties:

• (1, "area1", 5)
• (2, "area1", 3)
• (3, "area1", 2)
• (4, "area2", 4)
  GroupSize = 5, neighborhood = "area1"
  Output: [1] // Property 1 alone has capacity 5, which is optimal

Example 2:
Same properties, GroupSize = 6, neighborhood = "area1"
Output: [1, 3] // Properties 1+3 give capacity 7, which is minimal solution

Example 3:
Properties:

• (1, "area1", 5)
• (2, "area1", 3)
  GroupSize = 10, neighborhood = "area1"
  Output: [] // No combination can accommodate 10 people

def optimize_booking(properties, group_size, target_neighborhood):
    """
    Finds the optimal combination of properties to accommodate a group.
    
    Args:
        properties: List of (id, neighborhood, capacity)
        group_size: Minimum capacity required
        target_neighborhood: The neighborhood to search in
        
    Returns:
        List of property IDs or [] if no valid combination exists.
    """
    # 1. Filter properties by neighborhood
    filtered = [p for p in properties if p[1] == target_neighborhood]
    
    if not filtered:
        return []

    # 2. DP table: dp[total_capacity] = (property_count, list_of_ids)
    # We use a dictionary to store the best (minimum property count) combination for every possible capacity sum.
    dp = {0: (0, [])}
    
    for p_id, neighborhood, cap in filtered:
        new_entries = {}
        for current_cap, (count, ids) in dp.items():
            new_cap = current_cap + cap
            new_count = count + 1
            new_ids = ids + [p_id]
            
            # Update only if this capacity hasn't been reached yet, 
            # or if we found a way to reach it with fewer properties.
            if new_cap not in dp or new_count < dp[new_cap][0]:
                if new_cap not in new_entries or new_count < new_entries[new_cap][0]:
                    new_entries[new_cap] = (new_count, new_ids)
        
        dp.update(new_entries)
    
    # 3. Filter combinations that satisfy the group size
    candidates = {cap: info for cap, info in dp.items() if cap >= group_size}
    
    if not candidates:
        return []
    
    # 4. Find the minimum total capacity
    min_cap = min(candidates.keys())
    
    # 5. Return the IDs (sorted for consistency)
    best_combination_ids = candidates[min_cap][1]
    return sorted(best_combination_ids)

# --- Test Examples ---
properties = [
    (1, "area1", 5),
    (2, "area1", 3),
    (3, "area1", 2),
    (4, "area2", 4)
]

# Example 1: GS = 5, area1 -> Expected [1]
print(f"Example 1: {optimize_booking(properties, 5, 'area1')}")

# Example 2: GS = 6, area1 -> Expected [1, 3] (Cap 7 is min, 1+3 is better than 1+2 because both are same cap)
print(f"Example 2: {optimize_booking(properties, 6, 'area1')}")

# Example 3: GS = 10, area1 -> Expected []
print(f"Example 3: {optimize_booking(properties, 10, 'area1')}")