1 def optimize_booking(properties, group_size, target_neighborhood):
 2     """
 3     Finds the optimal combination of properties to accommodate a group.
 4     
 5     Args:
 6         properties: List of (id, neighborhood, capacity)
 7         group_size: Minimum capacity required
 8         target_neighborhood: The neighborhood to search in
 9         
10     Returns:
11         List of property IDs or [] if no valid combination exists.
12     """
13     # 1. Filter properties by neighborhood
14     filtered = [p for p in properties if p[1] == target_neighborhood]
15     
16     if not filtered:
17         return []
18 
19     # 2. DP table: dp[total_capacity] = (property_count, list_of_ids)
20     # We use a dictionary to store the best (minimum property count) combination for every possible capacity sum.
21     dp = {0: (0, [])}
22     
23     for p_id, neighborhood, cap in filtered:
24         new_entries = {}
25         for current_cap, (count, ids) in dp.items():
26             new_cap = current_cap + cap
27             new_count = count + 1
28             new_ids = ids + [p_id]
29             
30             # Update only if this capacity hasn't been reached yet, 
31             # or if we found a way to reach it with fewer properties.
32             if new_cap not in dp or new_count < dp[new_cap][0]:
33                 if new_cap not in new_entries or new_count < new_entries[new_cap][0]:
34                     new_entries[new_cap] = (new_count, new_ids)
35         
36         dp.update(new_entries)
37     
38     # 3. Filter combinations that satisfy the group size
39     candidates = {cap: info for cap, info in dp.items() if cap >= group_size}
40     
41     if not candidates:
42         return []
43     
44     # 4. Find the minimum total capacity
45     min_cap = min(candidates.keys())
46     
47     # 5. Return the IDs (sorted for consistency)
48     best_combination_ids = candidates[min_cap][1]
49     return sorted(best_combination_ids)
50 
51 # --- Test Examples ---
52 properties = [
53     (1, "area1", 5),
54     (2, "area1", 3),
55     (3, "area1", 2),
56     (4, "area2", 4)
57 ]
58 
59 # Example 1: GS = 5, area1 -> Expected [1]
60 print(f"Example 1: {optimize_booking(properties, 5, 'area1')}")
61 
62 # Example 2: GS = 6, area1 -> Expected [1, 3] (Cap 7 is min, 1+3 is better than 1+2 because both are same cap)
63 print(f"Example 2: {optimize_booking(properties, 6, 'area1')}")
64 
65 # Example 3: GS = 10, area1 -> Expected []
66 print(f"Example 3: {optimize_booking(properties, 10, 'area1')}")