Maximum Vacation Days with Minimum Flights
Problem statement
holidays[w][c] is the number of holiday days available in city c during week w. Choose exactly one city for each week and collect its holiday days. You may start in any city for free before the first week. Between consecutive weeks, staying costs no flight and moving to any other city costs one flight. Every pair of cities is connected; there is no flight matrix or travel-time deduction.
First maximize the total holiday days. Among all itineraries achieving that maximum, minimize the number of flights. Return [maximumDays, minimumFlights] in that order. An empty list of weeks returns [0,0]. You do not need to return the itinerary.
Function
vacationPlan(holidays: int[][]) → int[]Examples
Example 1
holidays = [[2,0,2],[3,0,3],[1,0,1],[0,0,2]]return = [8,0]Start in city 2 and stay there for all four weeks. It gives 2+3+1+2=8 days, the sum of the four weekly maxima, with zero flights. Starting in city 0 can also achieve eight days, but requires switching before the last week.
Example 2
holidays = [[7,0],[0,7],[7,0]]return = [21,2]The only maximum-day choices are cities 0,1,0. They give 21 days and require two flights. Staying in one city gives fewer days, so it cannot win by using fewer flights.
Example 3
holidays = []return = [0,0]With no weeks there are no holiday days and no transitions between cities.
Constraints
0 <= holidays.length <= 100- Every week contains the same number of city entries, between
1and50, inclusive. 0 <= holidays[w][c] <= 7