Tuesday, July 22, 2014

BigBurger

Problem:

TopCoder Problem Statement - BigBurder

Overview:

Simulate how long customers wait in line at a burger joint.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 149
04: Division: 2 / 1
05: Level: 2 / 1
06: Points: 500 / 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1648
08:  */
09: 
10: public class BigBurger {
11: 
12:     public int maxWait(int[] arrival, int[] service) {
13: 
14:         int maxWaitTime = 0;
15: 
16:         // Holds the time at which the customer's order is fullfulled.
17:         int[] orderFinishTime = new int[arrival.length];
18: 
19:         // Loop through all the customers.
20:         for (int i = 0; i < arrival.length; i++) {
21: 
22:             int startTime;
23: 
24:             if (i == 0) {
25:                 startTime = arrival[0];
26: 
27:             /*
28:              * At the earliest, the customer's start time is when they've
29:              * arrived.  If the previous order hasn't finished yet,
30:              * then they must wait until then.
31:              */
32:             } else {
33:                 startTime = Math.max(arrival[i], orderFinishTime[i - 1]);
34:             }
35: 
36:             orderFinishTime[i] = startTime + service[i];
37: 
38:             // Determine how long this customer had to wait.
39:             int waitTime = orderFinishTime[i] - service[i] - arrival[i];
40: 
41:             if (waitTime > maxWaitTime) {
42:                 maxWaitTime = waitTime;
43:             }
44:         }
45: 
46:         return maxWaitTime;
47:     }
48: }
Notes:

For each customer, we calculate the finish time for their order. For the first customer, that's just their arrival time plus the service time. For each remaining customer, it will either be their arrival time, or the finishing time of the customer ahead of them, plus the service time.

The first customer must be handled separately to avoid through an array index out of bounds exception on line 31.

Once we have the finish time for the customer, we calculate their wait time by subtracting off their arrival and service times. If this wait time is longer than any we've seen so far, save it in maxWaitTime.

As a side note, I found this to be pretty easy for a Division 2 - 500 Point problem. Compare it against BracketExpression which has the same point value.

No comments:

Post a Comment