Tuesday, July 22, 2014

WidgetRepairs

Problem:

TopCoder Problem Statement - WidgetRepairs

Overview:

Determine the number of days it will take a repair shop to work through the incoming items.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 150
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1346
08:  */
09:
10: public class WidgetRepairs {
11:
12:     public int days(int[] arrivals, int numPerDay) {
13:
14:         // Holds the number of items available to work on.
15:         int queue = 0;
16:
17:         // Counts the number of days worked.
18:         int workingDays = 0;
19:
20:         // Loop through each of the days.
21:         for (int arrival : arrivals) {
22:
23:             /*
24:              * Increment the queue by the number of items that arrived that
25:              * day.  If the queue is > 0, count it as a working day.
26:              * */
27:             queue += arrival;
28:             if (queue > 0) { workingDays++; }
29:
30:             // Remove from the queue the number of items processed in a day.
31:             queue -= numPerDay;
32:             if (queue < 0) { queue = 0; } // But dont' go below 0.
33:         }
34:
35:         // Work through the remaining items.
36:         while (queue > 0) {
37:             workingDays++;
38:             queue -= numPerDay;
39:         }
40:
41:         return workingDays;
42:     }
43: }
Notes:

Each day, the repair shop takes in a number of items, and works through some other number of items. This solution uses the variable queue to store any left over items that built up from previous days.

Any day that had items to work on (either from a previous day, or that arrived that day) are counted as a working day.

There's just two things to be careful of. First, when subtracting off the number of items that are processed in a day, make sure the queue doesn't go below zero - Line 32. And second, after items have stopped arriving, be sure to count the remaining days to work through the backlog - Lines 36-39

No comments:

Post a Comment