Finding the path with shortest waiting time

Question

I'm working on this problem, from a competition. I'll describe the problem in brief here.

A chef is trying to reach to a meeting before time T, but he wants to do that with minimum waiting time at bus stops. He doesn't mind taking long routes unless he reach his destination before T and wait the least at bus stops. He starts at station 1, and destination is the last station. Here's the input specification ...

N T M 
U V S E
U V S E
... and so on

where N is the number of stations, T is the meeting time and M is the number of buses. The next M lines are bus details. U is where a bus starts and V is where it reaches. S is the starting time and E is the reaching time. So a bus starts at station, U at time S and reaches station V at time E.

Constraints
2 ≤ N ≤ 50000
1 ≤ T ≤ 109
1 ≤ M ≤ 100000 (105)
1 ≤ U ≤ N
1 ≤ V ≤ N
U ≠ V
0 ≤ S < E ≤ 10

This is what I have tried, explanation follows after the code and in the code.

public int findMax(int nextStation, int rcd, int start, int end) {
    int tt = start - rcd;
    // If we reached destinaion, i.e the last station
    // no more wait has to be done and we return the time
    // required to reach here
    if (nextStation == noOfStations) {
        return tt;
    }

    // TODO : we already found a better path, so we skip this one
    // if (tt > minTillNow) {
    // return Integer.MAX_VALUE;
    // }

    List<Bus> buses = stations.get(nextStation);

    // If we have not reached finalStation
    // and there are no more buses from this station,
    // we reached a dead end.
    if (buses == null) {
        return -1;
    }

    int temp, min = Integer.MAX_VALUE;
    // If there are buses from this station, we try all
    // of them
    for (int i = 0; i < buses.size(); i++) {
        temp = findMax(buses.get(i).v, end, buses.get(i).s, buses.get(i).e);
        // Find minimum wait-time
        if (temp != -1 && temp < min) {
            min = temp;
        }
    }
    // If no subtree has a path
    if (min == Integer.MAX_VALUE) return -1;
    // if the wait to reach here is greater than any subsequent
    else if (min < tt) return tt;
    else
        return min;
}

I'm doing a DFS, starting at the first station and finding the max wait time along any path till the end and then choosing the minimum of all wait times along such paths. This works fine for the given input example..

Input:
5 10 5
1 2 1 2
1 5 3 4
2 4 4 5
2 5 5 6
4 5 6 7

Output:
2 

but fails when I submit it for some test input, with "Wrong Answer". Can someone spot a problem with the above approach? Also is this a good approach in general? What will be the complexity of this? I think it should be linear in M, is that right approximation.

Answer 1

This looks like a Google Code Jam problem. You can find the solutions others have made on their web site.

The problem with using depth first search is that it has geometrically increasing complexity. So, for example, if you had 10 stations and 10 connections from each station, you have 10^10 paths which is in the billions. It is like trying to brute force solve chess.

This kind of problem can be solved with dynamic programming (Code Jam loves DP problems). The reason why you know this is that the best move at any given station is independent of what stations you have been to previously. To solve the problem work backwards from the last station. You will always be able to find the minimum wait time for any particular move this way.

The only hitch is that the minimum wait time path may arrive after T.

To solve the problem you should therefore do a backtracking search over the minimum wait pathing. In other words, you do the DP solution as before, but keep track of how much total time is spent. If it exceeds T, then backtrack to the previous node and continue searching from there.

---

BTW avoid the use of meaningless variable names like "temp" and "i", it leads to mistakes.

Answer 2

I think what you're forgetting is to test whether you can still catch the bus in the for loop (as shown in my example below).

Apart from that, I think your code is more complicated than needed. For one, it is not very convenient to encode 'no path' by -1, because that requires extra testing when evaluating the minimum waiting time (I assume you have to return -1 if there is no path, but you can deal with that in the end).

I would propose the following function (and introduced new names for N and T, but I think they are meaningful enough).

public int minWaitingTime(int currentStop, int currentTime, int waitingTime) {
    if (currentStop == destination) {
        // reached the destination, return waitingTime if we met the deadline, 
        // or 'infinity' otherwise
        // NOTE: I assumed currentTime <= deadline is ok, maybe that should be <
        return currentTime <= deadline ? waitingTime : Integer.MAX_VALUE;
    } else {        
        List<Bus> buses = stations.get(currentStop);

        int min = Integer.MAX_VALUE;
        for (Bus bus : buses) {
            // test if we can still catch this bus
            if (bus.s <= currentTime) {
                // update minimum
                min = Math.min(min, 
                        minWaitingTime(bus.v, bus.e, 
                            waitingTime + (bus.s - currentTime));
            }
        }

        return min;
    }
}

You could now just call this as:

public int findMinWaitingTime() {
    int min = minWaitingTime(1, 0, 0);
    return min == Integer.MAX_VALUE ? -1 : min;
}

Btw, I hope this is an old competition and I'm not writing your solution now...