Wednesday, August 27, 2014

Salary

Problem:
TopCoder Problem Statement - Salary
Overview:

Determine an employee's compensation for the day. Rates vary for evening and night shifts.

Java Source:
01: public class Salary {
02: 
03:     private static String DAY_START = "06:00:00";
04:     private static String DAY_END = "17:59:59";
05: 
06:     /*
07:     * Converts the current time to the number of seconds since midnight
08:     */
09:     private static long convertTimeToSeconds(String time)  {
10: 
11:         String[] timeArray = time.split(":");
12:         int hours = Integer.parseInt(timeArray[0]);
13:         int minutes = Integer.parseInt(timeArray[1]);
14:         int seconds = Integer.parseInt(timeArray[2]);
15: 
16:         return (hours * 3600) + (minutes * 60) + seconds;
17:     }
18: 
19:     public int howMuch(String[] arrival, String[] departure, int wage) {
20: 
21:         /*
22:         * The number of seconds worked, modified for evening and night time.
23:         * To avoid using decimals (float or long), we'll count each day
24:         * shift second as 2, and each evening/night shift second as 3.
25:         * Then, at the very end, divide the total by 2.
26:         */
27:         long effectiveSecondsWorked = 0;
28: 
29:         // Markers for the start and end of the day shifts.
30:         long dayStart = convertTimeToSeconds(DAY_START);
31:         long dayEnd = convertTimeToSeconds(DAY_END);
32: 
33: 
34:         for (int i = 0; i < arrival.length; i++) {
35: 
36:             long shiftStart = convertTimeToSeconds(arrival[i]);
37:             long shiftEnd = convertTimeToSeconds(departure[i]);
38: 
39:             // Loop through each secod of the shift.
40:             for (long j = shiftStart; j < shiftEnd; j++)  {
41: 
42:                 /*
43:                 * If the current second is part of the day shift, increment the
44:                 * count by 2.
45:                 */
46:                 if ((j >= dayStart) && (j <= dayEnd))  {
47:                     effectiveSecondsWorked += 2;
48: 
49:                 /*
50:                 * If it's part of an evening or night shift, increment the count
51:                 * by 3.
52:                 */
53:                 } else  {
54:                     effectiveSecondsWorked += 3;
55:                 }
56:             }
57:         }
58: 
59:         /*
60:         * Multiply the wage by the number of hours worked.  Note that there are
61:         * 60 * 60 = 3600 seconds in an hour, but since we doubled that when
62:         * counting the seconds, we need to divide by 2 * 3600 = 7200
63:         */
64:         return (int) ((effectiveSecondsWorked * wage) / 7200);
65:     }
66: }
Notes:

The first thing to note is that you want to avoid using decimals. If you introduce doubles, you'll waste a ton of time tracking down off-by-one errors. To get around this, we simply double each second as we count it: A day shift second counts as 2; and an evening or night shift second will count as 3. Then, when the result is calculated, the number of seconds in an hour is also doubled to compensate.

The approach taken is to examine each second of the shift, and determine if it falls during the day shift hours or evening/night. The method convertTimeToSeconds() will give the number of seconds since the start of the day. We use that to set two markers; the start of the day shift and the end of the day shift. Then we loop through each of the shifts, and each second of each shift and compare that seconds agains the markers. The counter effectiveSecondsWorked is the incremented by either 2 or 3.

Once the effective total number of seconds is know, we multiple that by the wage, and divide by ther number of seconds in an hour times 2.

An alternative approach would be to determine the number of seconds in a shift by subtracting the start time from the end time. If a shift spans a night/day or day/evening boundary, then it would need to be broken into two (or more) segments. I had a solution using this approach about 99% done, but found a few tests that were off by 1 or 2. Frustrated, I re-wrote the solution using the current approach.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

No comments:

Post a Comment