Guests may want to visit multiple cities during one trip. Hotels in these cities offer various prices for the different days within the guest’s trip.
Your goal: find the cost of the trips that match the guest’s budget!
Input:
- The number of days the guest would like to stay at each city
- A budget (in EUR) the guest wants to spend at most for the entire trip
- A map containing the daily prices (in EUR) of the hotels in the cities the guest would like to visit during the trip
For the sake of simplicity, you can assume there is only one hotel per city in the input list, meaning all hotels in the list must be visited by the guest.
Output:
Sorted list (ascending) of prices for the trips matching the guest’s budget.
Example Input:
{
"numberOfDaysPerCity": 2,
"guestBudget": 309,
"dailyPricePerCity": {"Paris": [10,40,5,80,10,50],
"London": [60,30,20,70,50,70],
"Amsterdam": [20,80,20,50,80,100]
}
}Example output:
[220,240,250,305]Example trip that leads to a cost of 220:
- Day 1 and 2 in London costs 90 EUR
- Day 3 and 4 in Amsterdam costs 70 EUR
- Day 5 and 6 in Paris costs 60 EUR
This problem asks you to enumerate all possible trip costs for visiting multiple cities, where each city has daily hotel prices and must be stayed in for a fixed number of days. The core idea is to compute valid segment costs for each city and then use backtracking or DFS to explore city orders and accumulate total trip prices. Finally, return the distinct totals that do not exceed the guest's budget, sorted in ascending order.
