TopCoder problem "WizardsAppointments" used in TCHS09 Round 2 (Division I Level Three)

Problem Statement

    Several wizards have scheduled appointments to meet with non-wizards. Each wizard will have exactly one meeting with a non-wizard. Unfortunately, some of the wizards have just realized that they will not be able to arrive at their meetings on time. They will show up either too early or too late.

In an attempt to minimize the total waiting time, the wizards have decided to reschedule all of the meetings by shifting each one by the same amount of time. The total waiting time includes the time spent by wizards waiting for non-wizards to show up and the time spent by non-wizards waiting for wizards to show up. The non-wizards will all arrive exactly on time to the rescheduled meetings.

You are given int[]s scheduledTimes and arrivalTimes. The i-th element of scheduledTimes is the original scheduled starting time for the i-th wizard's meeting. The i-th element of arrivalTimes is the time when the i-th wizard will show up to his meeting. All times are given in hours. If you shift all the meetings by T hours, the total waiting time can be calculated as the sum of abs(scheduledTimes[i] + T - arrivalTimes[i]) over all the meetings. Return the number of distinct integer shifts which allow to minimize the total waiting time.


Parameters:int[], int[]
Method signature:int scheduleAdjustment(int[] scheduledTimes, int[] arrivalTimes)
(be sure your method is public)


-scheduledTimes will contain between 1 and 50 elements, inclusive.
-arrivalTimes will contain the same number of elements as scheduledTimes.
-Each element of scheduledTimes will be between 1 and 109, inclusive.
-Each element of arrivalTimes will be between 1 and 109, inclusive.


Returns: 1
The wizard will arrive at his meeting 1 hour earlier than the scheduled time. If the meeting is shifted 1 hour earlier, the total waiting time will be 0.
{20, 30}
{18, 25}
Returns: 4
Both wizards arrive too early, one of them being 2 hours early and the second one being 5 hours early. Every shift between -5 and -2 hours makes the total waiting time equal to 3 hours.
{10, 20}
{11, 17}
Returns: 5
This time, one wizard is late by 1 hour and the other is early by 3 hours. Every shift between -3 hours and 1 hour makes the total waiting time equal to 4 hours.
{10, 20, 30}
{13, 15, 34}
Returns: 1
Of the three wizards, one is 5 hours early and two are 3 and 4 hours late. After a 3 hour shift, one wizard comes in time, one is 8 hours early, and one is 1 hour late.
{10, 20, 30, 40}
{14, 24, 39, 37}
Returns: 1

Problem url:

Problem stats url:




PabloGilberto , Olexiy , ivan_metelsky

Problem categories: