The Limber Lambda

This is officially horribly embarrassing: 86 out of 250 points, and 1.5 hours later.  I simply could not get my mind around this one and out of sheer frustration ended up simulating the scenario (no doubt the most suboptimal solution) in painstaking detail.

This fast food joint has a queue (as they do), and a bunch of people arrive at integer value times provided in an array.  Congruent to this array is an array of integer durations of the same units indicating the time taken to serve the customer.  So if we have arrival = [1, 2, 3] and service = [10, 2, 10] then there are three customers, each arriving at time 1, 2 and 3 respectively; customer 1 has to wait 10 minutes for his order, customer 2, 2 minutes and customer 3, 10 minutes.  If consecutive customers arrive at the same time, they should be dealt with in the order in which they are encountered in the array.  The arrivals values will always be in non-descending order, and there won’t ever be a (fictitious) service of 0 minutes.  So, find the maximum time any one customer needs to wait to get to order.

It occurred to me that all of this isn’t very much help for anyone who chooses to try these problems themselves without benchmark input values and corresponding answers.  Here are the ones I worked against: {3, 3, 9} {2, 15, 14} = 11, {182} {11} = 0, {2,10,11} {3, 4, 3} = 3, {2,10,12} {15,1,15} = 7.

… and here’s my solution:

using System.Collections.Generic;

public class BigBurger
{
    public int maxWait(int[] arrival, int[] service)
    {
        int[] waitingTime = new int[arrival.Length];
        Queue<int> queue = new Queue<int>();
        int maxwait = 0;
        int index = 0;
        int time = 0;
        int lastStart = 0;
        bool started = false;
        while (queue.Count > 0 | !started | index < arrival.Length)
        {
            time++;
            foreach (int v in queue)
            {
                waitingTime[v]++;
            }
            if (queue.Count > 0 && (time - lastStart) >= service[queue.Peek()])
            {
                queue.Dequeue();
                lastStart = time;
                if (queue.Count == 0 && index < arrival.Length)
                {
                    started = false;
                }
            }
            while (index < arrival.Length && arrival[index] == time)
            {
                if (!started)
                {
                    lastStart = time;
                    started = true;
                }
                queue.Enqueue(index);
                index++;
            }
        }
        for (int i = 0; i < waitingTime.Length; i++)
        {
            maxwait = maxwait < (waitingTime[i]-service[i]) 
                ? (waitingTime[i]-service[i]) : maxwait;
        }
        return maxwait;
    }
}