We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Vacation Days

Number: 568

Difficulty: Hard

Paid? Yes

Companies: Meta, Datadog, Google

Problem Description

Jack has n cities available and k weeks to travel. Each city provides a fixed number of vacation days per week, given in an n x k matrix, and the cities are connected with direct flights represented by an n x n matrix. Jack starts in city 0 on Monday and can only fly (or stay) on Monday mornings. The goal is to maximize the total vacation days Jack can take over k weeks, following the travel constraints.

Key Insights

  • Use dynamic programming to keep track of the maximum vacation days possible up to each week.
  • Define dp[week][city] as the maximum vacation days accumulated up to that week when ending in the specified city.
  • Transition from week i-1 to week i by considering all cities from which a flight (or staying) to the current city is possible (including self-transitions).
  • Iterate week by week, updating the state based on available flights and the city's available vacation days.
  • The final answer is the maximum value across all cities after k weeks.

Space and Time Complexity

Time Complexity: O(k * n^2), where k is the number of weeks and n is the number of cities. Space Complexity: O(n * k) if using a 2D DP array; can be optimized to O(n) using rolling arrays.

Solution

We use dynamic programming where the state dp[week][city] represents the maximum vacation days achievable up to that week if ending in the given city. For each week, iterate through each city and check all previous cities from which a valid flight (or staying in the same city) is possible. Update the dp state with the maximum vacation days so far by adding the vacation days available in the destination city for that week. Finally, the maximum value in the last week across all cities is the answer.

Code Solutions

# Python solution using dynamic programming

def maxVacationDays(flights, days):
    n = len(flights)        # number of cities
    k = len(days[0])        # number of weeks
    
    # Initialize dp table for week 0 with -infinity to identify unreachable states.
    dp = [[-float('inf')] * n for _ in range(k)]
    
    # On week 0, we can only be in city 0 or we can fly to other cities if a flight exists from city 0.
    for city in range(n):
        if city == 0 or flights[0][city] == 1:
            dp[0][city] = days[city][0]  # vacation days in first week
 
    # Fill DP for subsequent weeks
    for week in range(1, k):
        for currentCity in range(n):
            # Consider all previous cities that allow us to get to currentCity
            for prevCity in range(n):
                # If it is possible to fly or stay (self flight is allowed as per problem understanding)
                if dp[week-1][prevCity] != -float('inf') and (prevCity == currentCity or flights[prevCity][currentCity] == 1):
                    dp[week][currentCity] = max(dp[week][currentCity],
                                                dp[week-1][prevCity] + days[currentCity][week])
    
    # The answer is the maximum vacation days achievable at the end of k weeks in any city
    return max(dp[k-1])

# Example usage:
# flights = [[0,1,1],[1,0,1],[1,1,0]]
# days = [[1,3,1],[6,0,3],[3,3,3]]
# print(maxVacationDays(flights, days))  # Expected output: 12
← Back to All Questions