You are given a list of properties, each Property(id: int, neighborhood: string, capacity: int). Given a targetNeighborhood (string) and groupSize (int), return the IDs of a combination of properties drawn only from targetNeighborhood such that:
-
the total capacity is at least groupSize;
-
among all feasible combinations, the number of selected properties is minimized;
-
if multiple combinations have the same minimal count, choose one whose total capacity is minimal (i.e., as close to groupSize as possible above it);
-
if no feasible combination exists, return [].
Specify and implement an optimal algorithm. Describe:
-
the approach and data structures,
-
time and space complexity,
-
how you handle ties deterministically (e.g., smallest total capacity, then lexicographically smallest ID list),
-
edge cases (e.g., duplicate capacities/IDs, very large inputs).
Example input:
Properties = [
Property(1, "downtown",
5),
Property(2, "downtown",
3),
Property(3, "downtown",
1),
Property(4, "uptown",
4),
Property(5, "uptown",
2)
]
targetNeighborhood = "downtown"
-
groupSize = 6 -> one valid answer is [1, 3]
-
groupSize = 3 -> [2]
-
groupSize = 16 -> []
Note: With targetNeighborhood = "downtown" and groupSize = 10, no solution exists because the capacities of downtown properties sum to 9.