The Limber Lambda

Lesson learned–there’s a way of approaching TopCoder problems, and speeding through the problem description (missing some important, sometimes subtle hints as you go) is not the way.  Give yourself some time, maybe pull out a pencil and paper, doodle a bit, let your mind free.  Only then do you avail yourself of that light-bulb moment.

So, it turns out that the fast-food joint problem really isn’t that hard at all.  In a nutshell the time that a customer waits can be summed up as follows:

Wait_n = Arrival₀ – Arrival_n + Wait_n-1 + Service_n-1

… but only if Arrival₀ + (Wait_n-1 + Service_n-1) is later than (greater than) Arrival_n, otherwise Wait_n = 0

… and of course, Wait₀ = 0

That’s it–here’s the source:

public class BigBurger
{
    private int _MaxWait = 0;

    public int maxWait(int[] arrival, int[] service)
    {
        _MaxWait = 0;
        WaitFor(arrival, service, arrival.Length-1);
        return _MaxWait;
    }

    private int WaitFor(int[] arrival, int[] service, int ix)
    {
        if (ix == 0)
            return 0;
        int w = WaitFor(arrival, service, ix - 1) + service[ix - 1];
        w = (arrival[0] + w) > arrival[ix] ? arrival[0] + w - arrival[ix] : 0;
        _MaxWait = _MaxWait < w ? w : _MaxWait;
        return w;
    }
}