This page explains Java solution to problem Maximum Vacation Days
using Priority Queue
data structure.
LeetCode 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.
N
cities, represented by indexes from 0
to N-1
. Initially, you are in the city indexed 0
on Monday.N * N
matrix (not necessary 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
.K
weeks (each week has 7
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 don't consider the impact of flight time.N * K
matrix called days representing this relationship. For the value of days[i][j]
, it represents the maximum days you could take vacation in the city i
in the week j
.
You're given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K
weeks.
Example 2:Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation: Ans = 6 + 3 + 3 = 12.
Example 3:Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
Output: 3
Explanation: Ans = 1 + 1 + 1 = 3.
Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
Output: 21
Explanation: Ans = 7 + 7 + 7 = 21.
package com.vc.hard;
import java.util.*;
class MaximumVacationDays {
public int maxVacationDays(int[][] flights, int[][] days) {
int n = flights.length;
int k = days[0].length;
Comparator<int[]> comparator = new Comparator<int[]>(){
public int compare(int[] x, int[] y) {
return Integer.compare(y[1], x[1]);
}
};
PriorityQueue<int[]> heap = new PriorityQueue<int[]>(comparator);
heap.add(new int[]{0, 0});
for (int week = 0; week < k; week++) {
PriorityQueue<int[]> nextHeap = new PriorityQueue<int[]>(comparator);
while (!heap.isEmpty() && nextHeap.size() < n) {
int[] origin = heap.poll();
int from = origin[0];
int vacationDays = origin[1];
for (int to = 0; to < n; to++) {
if (to == origin[0] || flights[from][to] == 1) {
nextHeap.add(new int[]{to, vacationDays + days[to][week]});
}
}
}
heap = nextHeap;
}
return heap.remove()[1];
}
}
O(K * log N) Where
K is total number of weeks
N is total number of cities
O(N) Where
N is total number of cities