Java A* Search solution.


  • 0

    Instead of finding the maximum vocation days, we can convert the question into finding the minimum work days.
    For example, if the vocation days of a week is 1, then the work days is 7-1=6.
    Therefore, A* search can be applied to solve this problem.
    The vocation days is ( 7 * K ) - min(work days).

    public class Solution {
        class WeekLoc {
            int week, city, workday;
            int key;
            WeekLoc(int week, int city) {
                this.week = week;
                this.city = city;
                key = (city * 100) + week;
                workday = 0;
            }
        }
        class WeekLocComp implements Comparator<WeekLoc> {
            public int compare(WeekLoc w1, WeekLoc w2) {
                return w1.workday - w2.workday;
            }
        }
        public int maxVacationDays(int[][] flights, int[][] days) {
            int N = flights.length, K = days[0].length;
            PriorityQueue<WeekLoc> queue = new PriorityQueue(1, new WeekLocComp());
            Set<Integer> visited = new HashSet<>();
            queue.offer(new WeekLoc( -1, 0 ));
            while (! queue.isEmpty() ) {
                WeekLoc cur = queue.poll();
                //System.out.println("week:"+cur.week+" city:"+cur.city + " day:" + cur.workday );
                if (cur.week == K-1) return 7*K - cur.workday;
                for (int i = 0 ; i < N; i++) {
                    if ( i == cur.city || flights[cur.city][i] == 1 ) {
                       WeekLoc next = new WeekLoc(cur.week+1, i);
                       if (! visited.contains(next.key) ) {
                           next.workday = cur.workday + ( 7 - days[next.city][next.week]);
                           queue.offer(next);
                           visited.add(next.key);
                       }
                    }
                }
            }
            return 0;
        }
    }
    

  • 0

    Is it necessary to treat it as A*? It's a simple BFS.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.