|
| 1 | +package com.fishercoder.solutions; |
| 2 | + |
| 3 | +import java.util.Arrays; |
| 4 | + |
| 5 | +/** |
| 6 | + * 568. Maximum Vacation Days |
| 7 | + * |
| 8 | + * LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. |
| 9 | + * But all work and no play makes Jack a dull boy, |
| 10 | + * you could take vacations in some particular cities and weeks. |
| 11 | + * Your job is to schedule the traveling to maximize the number of |
| 12 | + * vacation days you could take, but there are certain rules and restrictions you need to follow. |
| 13 | +
|
| 14 | + Rules and restrictions: |
| 15 | + 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. |
| 16 | + The cities are connected by flights. |
| 17 | + The flights are represented as a N*N matrix (not necessary symmetrical), |
| 18 | + called flights representing the airline status from the city i to the city j. |
| 19 | + If there is no flight from the city i to the city j, flights[i][j] = 0; |
| 20 | + Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i. |
| 21 | +
|
| 22 | + You totally have K weeks (each week has 7 days) to travel. |
| 23 | + You can only take flights at most once per day and can only take flights on each week's Monday morning. |
| 24 | + Since flight time is so short, we don't consider the impact of flight time. |
| 25 | + For each city, you can only have restricted vacation days in different weeks, |
| 26 | + given an N*K matrix called days representing this relationship. |
| 27 | + For the value of days[i][j], it represents the maximum days you could take vacation in the city i in the week j. |
| 28 | + You're given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks. |
| 29 | +
|
| 30 | + Example 1: |
| 31 | + Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] |
| 32 | + Output: 12 |
| 33 | + Explanation: |
| 34 | + Ans = 6 + 3 + 3 = 12. |
| 35 | +
|
| 36 | + One of the best strategies is: |
| 37 | + 1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. |
| 38 | + (Although you start at city 0, we could also fly to and start at other cities since it is Monday.) |
| 39 | + 2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days. |
| 40 | + 3rd week : stay at city 2, and play 3 days and work 4 days. |
| 41 | +
|
| 42 | +
|
| 43 | + Example 2: |
| 44 | + Input:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]] |
| 45 | + Output: 3 |
| 46 | + Explanation: |
| 47 | + Ans = 1 + 1 + 1 = 3. |
| 48 | +
|
| 49 | + Since there is no flights enable you to move to another city, you have to stay at city 0 for the whole 3 weeks. |
| 50 | + For each week, you only have one day to play and six days to work. |
| 51 | + So the maximum number of vacation days is 3. |
| 52 | +
|
| 53 | +
|
| 54 | + Example 3: |
| 55 | + Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]] |
| 56 | + Output: 21 |
| 57 | + Explanation: |
| 58 | + Ans = 7 + 7 + 7 = 21 |
| 59 | +
|
| 60 | + One of the best strategies is: |
| 61 | + 1st week : stay at city 0, and play 7 days. |
| 62 | + 2nd week : fly from city 0 to city 1 on Monday, and play 7 days. |
| 63 | + 3rd week : fly from city 1 to city 2 on Monday, and play 7 days. |
| 64 | +
|
| 65 | + Note: |
| 66 | + N and K are positive integers, which are in the range of [1, 100]. |
| 67 | + In the matrix flights, all the values are integers in the range of [0, 1]. |
| 68 | + In the matrix days, all the values are integers in the range [0, 7]. |
| 69 | + You could stay at a city beyond the number of vacation days, |
| 70 | + but you should work on the extra days, which won't be counted as vacation days. |
| 71 | + If you fly from the city A to the city B and take the vacation on that day, |
| 72 | + the deduction towards vacation days will count towards the vacation days of city B in that week. |
| 73 | + We don't consider the impact of flight hours towards the calculation of vacation days. |
| 74 | + */ |
| 75 | +public class _568 { |
| 76 | + |
| 77 | + /**credit: https://leetcode.com/articles/maximum-vacation-days/#approach-2-using-dfs-with-memoization-accepted*/ |
| 78 | + public int maxVacationDays(int[][] flights, int[][] days) { |
| 79 | + int[][] memo = new int[flights.length][days[0].length]; |
| 80 | + for (int[] l: memo) { |
| 81 | + Arrays.fill(l, Integer.MIN_VALUE); |
| 82 | + } |
| 83 | + return dfs(flights, days, 0, 0, memo); |
| 84 | + } |
| 85 | + |
| 86 | + public int dfs(int[][] flights, int[][] days, int cur_city, int weekno, int[][] memo) { |
| 87 | + if (weekno == days[0].length) |
| 88 | + return 0; |
| 89 | + if (memo[cur_city][weekno] != Integer.MIN_VALUE) |
| 90 | + return memo[cur_city][weekno]; |
| 91 | + int maxvac = 0; |
| 92 | + for (int i = 0; i < flights.length; i++) { |
| 93 | + if (flights[cur_city][i] == 1 || i == cur_city) { |
| 94 | + int vac = days[i][weekno] + dfs(flights, days, i, weekno + 1, memo); |
| 95 | + maxvac = Math.max(maxvac, vac); |
| 96 | + } |
| 97 | + } |
| 98 | + memo[cur_city][weekno] = maxvac; |
| 99 | + return maxvac; |
| 100 | + } |
| 101 | + |
| 102 | +} |
0 commit comments