Coding

Maximum Vacation Days

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

TakeUforward wants to give one of its best employees the option to travel among n cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

Rules and restrictions:

You can only travel among n cities, represented by indexes from 0 to n - 1. Initially, you are in the city indexed 0 on Monday.
The cities are connected by flights. The flights are represented as an n x n matrix (not necessarily symmetrical), called flights representing the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] == 0; Otherwise, flights[i][j] == 1. Also, flights[i][i] == 0 for all i.
You totally have k weeks (each week has seven days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we do not consider the impact of flight time.
For each city, you can only have restricted vacation days in different weeks, given an n x k matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take a vacation in the city i in the week j.
You could stay in a city beyond the number of vacation days, but you should work on the extra days, which will not be counted as vacation days.
If you fly from city A to city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.
We do not consider the impact of flight hours on the calculation of vacation days.

Given the two matrices flights and days, return the** maximum** vacation days you could take during** k weeks.**

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[2,4,2],[7,1,4],[4,4,4]] Output: 15

Explanation: One of the best strategies is: 1st week : fly from city 0 to city 1 on Monday, and play 7 days and work 0 day. 2nd week : fly from city 1 to city 2 on Monday, and play 4 days and work 3 days. 3rd week : stay at city 2, and play 4 days and work 3 days. Ans = 7 + 4 + 4 = 15.

Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,2,3],[7,7,7],[7,7,7]] Output: 6

Explanation: **Here,you have to stay at city 0 for the whole 3 weeks. ** For each week, you only have one day to play and six days to work. So the maximum number of vacation days is 6. Ans = 1 + 2 + 3 = 6.

Input: flights = [[0,0,1],[1,0,0],[1,1,1]], days = [[2,4,4],[7,2,5],[6,3,4]]

n == flights.length
n == flights[i].length
n == days.length
k == days[i].length
1 <= n, k <= 100
flights[i][j] is either 0 or 1.0 <= days[i][j] <=

cpp

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        // User code goes here
    }
};

java

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        // User code goes here
    }
}

python

class Solution:
    def maxVacationDays(self, flights, days):
       # User code goes here

javascript

class Solution {
    maxVacationDays(flights, days) {
        // User code goes here
    }
}

csharp

public class Solution {
    public int MaxVacationDays(int[][] flights, int[][] days) {
        
    }
}

func maxVacationDays(flights [][]int, days [][]int) int {
    // User code goes here
}

Stuck? Show a way to structure it+

01Define dp[week][city] as best vacation arriving there.
02Initialize only the starting city.
03For each week consider staying and permitted flights.
04Add that destination's vacation days.
05Take the maximum over cities after the last week.

Reference answer

Use DP by week and city. dp[c] before a week is the best number of vacation days achievable while being in city c; initialize city zero to 0 and every other state to negative infinity. For each week create next, and from every reachable city consider staying plus every outgoing flight. If you land in destination d, update next[d] with dp[c] + days[d][week]. Replace the vector after the week, then answer with the maximum final state. This models the important detail that flights occur before consuming that week's days. With an adjacency matrix the cost is O(W*C^2) and space is O(C); adjacency lists reduce transitions on sparse flight graphs.

Then expect these follow-ups

How would you reconstruct the itinerary?
Tests: parent pointers
How does a flight cost change the recurrence?
Tests: weighted transitions

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question