Problem Statement |
| | In Olympic boxing, there are five judges who press a button when they think
that a particular boxer has just landed a punch. The times of the button
presses are recorded, and the boxer receives credit for a punch if at least
three of the judges press their buttons within 1 second of each other.
This "algorithm" needs a lot of refinement. Here is the version that you
should implement.
Find the maximum number of disjoint time intervals that can be chosen such that
each interval is of duration 1 second or less and contains button presses from
at least 3 different judges. Two intervals are disjoint if every time within one interval is
strictly less than every time in the other. We give the boxer credit for one punch during
each interval.
The duration of an interval is the amount of time between the instant when it starts and when it
ends, and a punch may be included in an interval if its recorded time is
at the start, end, or in between.
So, for example, the interval from 1 to 4 has duration 3, and a punch recorded at time 1, 2, 3, or 4
is in that interval. The intervals 1 to 4 and 5 to 22 are disjoint, but the intervals 1 to 4 and 4 to
22 are not disjoint.
Create a class Boxing that contains a method maxCredit that is given five int[]s,
a, b, c, d, and e, representing the times of the button presses of the five judges
in milliseconds. The method returns the maximum credits that can be given to the
boxer.
|
| |
Definition |
| | | Class: | Boxing | | Method: | maxCredit | | Parameters: | int[], int[], int[], int[], int[] | | Returns: | int | | Method signature: | int maxCredit(int[] a, int[] b, int[] c, int[] d, int[] e) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | Each of the five arguments will contain between 0 and 50 elements inclusive. |
| - | Each element of each of the arguments will be between 0 and 180,000 inclusive. |
| - | The elements within each of the arguments will be in strictly increasing order. |
| |
Examples |
| 0) | |
| | {1,2,3,4,5,6} | {1,2,3,4,5,6,7} | {1,2,3,4,5,6} | {0,1,2} | {1,2,3,4,5,6,7,8} |
| Returns: 6 | |
This match had a fast start, with 6 punches credited in the first 6
milliseconds of the match! One way to choose 6 disjoint intervals is
to choose [1,1], [2,2], [3,3], [4,4], [5,5], [6,6] each of which
contains button presses from judges a, b, and c.
There are three button presses in the time interval from
7 through 8, but
only from two different judges so no additional credit can be given.
|
|
|
| 1) | |
| | {100,200,300,1200,6000} | {} | {900,902,1200,4000,5000,6001} | {0,2000,6002} | {1,2,3,4,5,6,7,8} |
| Returns: 3 | |
One way to form three intervals is [0,1000], [1001,2000], [6000,6002]
|
|
|
| 2) | |
| | {5000,6500} | {6000} | {6500} | {6000} | {0,5800,6000} |
| Returns: 1 | |
Any interval that doesn't include 6000 will not have enough button presses,
so we can form only one disjoint interval with credit for a punch.
|
|
|