Java neat solution using Dijkstra! (45/47 completed, TLE at 46th test)


  • 0
    N

    The idea is to use Dijkstra for finding shortest path as following:

    • Find maximum value (maxVal) in days.
    • maxVal += 1
    • Subtract all days values from maxVal
    • Now we can use Dijkstra to find the shortest path. We can easily compute neighbors based on flights.
    • Note: Updating an element in PriorityQueue requires O(n), this is why instead I use the trick in the NOTE in page 2 here: https://activities.tjhsst.edu/sct/lectures/1314/dijkstra_10_30_13.pdf.
    • At the end, return numberOfWeeks * maxValue - shortest Path value.
    private Comparator<int[]> StateComparator = new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            assert a != null && b != null;
            return a[0] - b[0];
        }
    };
    
    public int maxVacationDays(int[][] flights, int[][] days) {
        int maxVal = 0;
        for (int i = 0; i < days.length; i++) {
            for (int j = 0; j < days[i].length; j++) {
                if (days[i][j] > maxVal)
                    maxVal = days[i][j];
            }
        }
    
        maxVal++;
        for (int i = 0; i < days.length; i++) {
            for (int j = 0; j < days[i].length; j++) {
                days[i][j] = maxVal - days[i][j];
            }
        }
    
        int cities = days.length;
        int weeks = days[0].length;
        boolean[][] visited = new boolean[cities][weeks];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(cities, StateComparator);
        for (int city = 0; city < cities; city++) {
            if (city == 0 || flights[0][city] == 1)
                pq.add(new int[] { days[city][0], city, 0 });
        }
    
        while (!pq.isEmpty()) {
            int[] min = pq.peek();
            pq.remove();
            int dist = min[0];
            int city = min[1];
            int week = min[2];
    
            if (visited[city][week])
                continue;
    
            visited[city][week] = true;
            int nextWeek = week + 1;
            if (nextWeek == weeks) // stop condition
                return weeks * maxVal - dist;
    
            for (int nextCity = 0; nextCity < cities; nextCity++) {
                if (city == nextCity || flights[city][nextCity] == 1)
                    pq.add(new int[] { dist + days[nextCity][nextWeek], nextCity, nextWeek });
            }
        }
    
        assert false;
        return 0;
    }

Log in to reply
 

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