Leetcode: Maximum Vacation Days

 

This question is asked very frequently at Facebook and Google. 

Let's say an employee has the option to travel among n cities. I want to schedule the traveling to maximize the number of vacation days that I am able to take. However, there are a few rules that I have to follow.

I can only travel among n cities with indexes 0 to n - 1 and the city indexed 0 is on Monday. 

The cities are connected by flights in a graph where flights[i][j] (0/1) represents if there is a flight from city i to city j. 

I have a total of k weeks with 7 days to travel, and can only take flights once a day on each week's Monday morning. 

Each city has restrictions in the amount of vacation days I can take in a week given n x k matrix days. days[i][j] is the maximum days I can take vacation in city i in the week j. 

I should work on the remainder of the weeks not allocated inside of the days matrix. 

Flying from city A to city B will count as a vacation day to city B, and the flight hour impact is negligible. Maximize number of vacation days. 

Example Problem: 

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

Output: 12

 Explanation: One of the best strategies is: 

1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.

(Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 

2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days. 

3rd week : stay at city 2, and play 3 days and work 4 days. 

Ans = 6 + 3 + 3 = 12.

The idea of dynamic programming is pretty simple. The number of vacation that can be taken given starting from the ith city in the jth week is not dependent on vacation taken earlier weeks, but the ones that are taken in the subsequent weeks and connections. 

There are 2 cases for dynamic programming:

1. Start from the ith city in the kth city and stay in the citythe k + 1 weeks so dp[i][k] = dp[i][k + 1] + days[i][k].

2. Start from the ith city in kth week and move to the jth city in the k + 1th week. Flights[i][j] should be 1 for this. 

We can move to any jth city such that a connection exists between the ith city and the kth city. We neeed to choose the destination however, that maximize the number of vacations and use this maximum value to update the dynamic programming value. Maximize maxdays[j][k] + days[j][k + 1]. 

C++ mainly just updates true and false cases. 

Here's the C++: 

class Solution {

    public: 

        int maxVacationDays(vector<vector<int>> &flights, vector<vector<int>> &days) {

            int n = days.size();  //city

            int k = days[0].size();  //number of weeks

            vector<vector<int>> dp (n, vector<int>(k, 0)); //dp[i][j] = max days play if you spent week j in city i. 

            //dp step going down to the left. 

            for(int j = k - 1; j >= 0; j--) {

                for(int i = 0; i < n; i++) {

                    //assign this to the days array for one city to another. 

                    dp[i][j] = days[i][j]; //the number of days you can stay in city i on week j. 

                    for(int i1 = 0; i1 < n && j < k - 1; i1++) {

                        if(i == i1 || flights[i][i1]) {

                            //taks maximum of number of days you can stay in the city vs going to an alternative city in the following week. Staying in the city vs moving to another city. 

                            dp[i][j] = max(dp[i][j], days[i][j] + dp[i1][j + 1]); 

                        }

                    }

                }

            }

            int maxplay = dp[0][0]; 

            for(int i = 1; i < n; i++) {

                if(flights[0][i]) {

                    //go back to week 0 and return the maximum resulting start city. 

                    maxplay = max(maxplay, dp[i][0]); 

                }

            }

            //maximize playtime. 

            return maxplay; 

        }

};