Practice/Meta/Leetcode 568. Maximum Vacation Days

Leetcode 568. Maximum Vacation Days

CodingMust

Problem

You're planning an extended vacation across multiple cities over several weeks. You start in city 0 and need to maximize the total number of vacation days you can enjoy.

You are given:

• A 2D array flights where flights[i][j] equals 1 if there is a direct flight from city i to city j, and 0 otherwise. Note that flights[i][i] equals 0 or 1, indicating whether you can stay in city i.
• A 2D array days where days[i][k] represents the number of vacation days you can enjoy in city i during week k.

At the beginning of each week, you can choose to either:

• Stay in your current city (if flights[currentCity][currentCity] equals 1 or you just want to stay), or
• Fly to another city j (if flights[currentCity][j] equals 1)

Return the maximum number of vacation days you can accumulate over all weeks.

Requirements

1. You must start at city 0
2. You can only travel along routes where flights[i][j] equals 1
3. Each week, you collect vacation days based on which city you're in
4. You must decide your location at the start of each week
5. Return the maximum total vacation days possible

Constraints

• n == flights.length (number of cities)
• n == flights[i].length
• n == days.length
• k == days[i].length (number of weeks)
• 1 <= n, k <= 100
• flights[i][j] is either 0 or 1
• 0 <= days[i][j] <= 7

Examples

Example 1:

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

• Start at city 0
• Week 0: Fly to city 1, collect 3 vacation days
• Week 1: Stay at city 1, collect 2 vacation days
• Total: 3 + 2 = 7 vacation days `

Example 2:

` Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]] Output: 3 Explanation:

• No flights available between cities
• Must stay at city 0 for all 3 weeks
• Total: 1 + 1 + 1 = 3 vacation days `

Example 3:

` Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[3,1,3],[1,3,1]] Output: 12 Explanation:

• Start at city 0
• Week 0: Fly to city 1, collect 3 vacation days
• Week 1: Fly to city 2, collect 3 vacation days
• Week 2: Fly to city 1, collect 3 vacation days
• Alternative optimal paths exist, total: 12 vacation days `