PROBLEM STATEMENT
After the last TopCoder match, people kept logging in to ask if the system
tests had started already. Given a list of people and what times they came in
to whine, figure out the minimum number of reassurances the admins had to give
during the night.
All times will be listed in minutes since the contest finished. The admin has
to give a reassurance within 10 minutes (inclusive) after, or up to 5 minutes
(inclusive) before. This means that if an admin gives a reassurance at time x,
he covers all of the whines from time x-10 to time x+5, inclusive.
Each element in the input String[] will consist of a name followed by a list of
times, with a single space after the name and each time separated by a single
space.
Example:
whiners = {"ZorbaTHut 1 61 121",
"Echo 16 71 151"}
Both Echo and ZorbaTHut can be placated with a reassurance at 11 (covering
ZorbaTHut's whine at time 1 and Echo's whine at time 16), as well as a
reassurance at 66 (covering ZorbaTHut's whine at time 61, and Echo's whine at
time 71). Each require an additional reassurance that can't be overlapped, one
around 121 for ZorbaTHut and one around 151 for Echo.
A total of 4 would be required so the method would return 4.
Example:
whiners = {"ZorbaTHut 1 1 1 21 6 11 16 26 31 36"}
With just two reassurances, one at 11 (covering 1-16) and one at 31 (covering
21-36), ZorbaTHut will be ok.
the method would return 2
DEFINITION
Class: Whiners
Method: minReplies
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int minReplies(String[]
whiners);
NOTES
- times may be duplicated within the same element
- times may be duplicated between elements
- names may be duplicated between elements
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- whiners will have between 0 and 20 elements, inclusive
- each element will contain between 3 and 50 characters, inclusive
- each element will consist of a name followed by a single space, followed by a
list of times where each time is separated by exactly one space
- there will be no trailing or leading spaces in an element
- the name will contain only the letters A-Z and a-z
- the name will contain between 1 and 20 characters, inclusive
- there will be between 1 and 24 times, inclusive, per element
- each time will be between 1 and 1000, inclusive
- times will not have leading zeroes
EXAMPLES
(1)
whiners = {"loser 1"}
the method would return 1
(2)
whiners = {}
the method would return 0
(3)
whiners = {"A 16 32 48 64 80 96 112 128 144 160 176 192"}
the method would return 12
(4)
whiners = {"B 15 30 45 60 75 90 105 120",
"B 120 105 90 75 60 45 30 15"}
the method would return 4
(5)
whiners = {"Echo 1 134 28 17 17 19 100 12 985 324",
"dok 14 293 48 231 18 101 23 44 44",
"ZorbaTHut 1 2 3 4 5 6 7 8 9 10 11",
"RandomGuyHasLongName 200 200 200 200 200"}
the method would return 10
(6)
whiners = {"PatientGuy 500 1000"}
the method would return 2