Problem Statement
You want to send some messages of various lengths (specified in the number of minutes it takes to send them), and don't want more than three of them to be completely intercepted. A message is considered to be intercepted if some malevolent person taps your connection the whole time the message is being sent (a partially tapped message won't do this person any good). Assuming that the connection is being tapped during interceptTime consecutive minutes, what's the shortest time you need to send all the messages so at most three of the messages can be completely intercepted?
Each message is sent in one continuous transmission, though any number of messages can be sent in parallel. You can only start sending a message at the beginning of a minute. The messages can be sent in any order.
Create a class ShortTaps containing the method leastTime which takes an int interceptTime and a int[] messageTimes (containing the time in minutes it takes to send each message, respectively) and returns an int, the minimum time needed to send all the messages so that at most three of them can be intercepted.
Definition
- Class:
- ShortTaps
- Method:
- leastTime
- Parameters:
- int, int[]
- Returns:
- int
- Method signature:
- int leastTime(int interceptTime, int[] messageTimes)
- (be sure your method is public)
Constraints
- interceptTime will be between 1 and 100, inclusive.
- messageTimes will contain between 1 and 50 elements, inclusive.
- Each element in messageTimes will be between 1 and 100, inclusive.
Examples
10
{2, 3, 4, 5, 6, 7, 8}Returns: 14
The optimal solution can be achieved by sending the messages according to this scheme: Time Message length --------------------- 0 2 min, 3 min, 6 min 3 8 min 6 5 min 7 4 min, 7 min20
{14, 2, 9, 14, 17, 1, 3, 10, 5, 9, 25, 8, 11, 7}Returns: 43
40
{30, 40, 50, 60, 70, 80, 90, 100}Returns: 100
Only the two shortest messages have any chance of being intercepted, so all eight messages can be sent at time 0.
Back to all problems