Problem Statement |
| |
The celebrated general Archibald Waving took charge of the fourth army in the occidental front.
After losing the first three armies, Waving has become obsessed with effective synchronization of the army.
Whenever Waving needs to write the time at which military operations will be performed, he writes only the
minute part of the time (the time also has an hour part, which Waving does not write down). This
strategy prevents the enemy from figuring out the exact times of the operations even if he obtains the
schedule written by Archibald Waving. Of course, Waving's soldiers are very smart, so they are able to
reconstruct the entire schedule from the minute parts alone.
A particular time can be written as AB:CD, where AB represents the hour part, and CD represents the minute part.
The schedule is a list of times within the same day, where time can lie in the range from 00:00 to 23:59.
Moreover, the times appear in chronological order, i.e. the time of the operation performed earlier
should be listed before the time of the operation performed later during the day. Also, no two
operations can be performed at the same time.
Waving wants to know if the enemy will be able to figure out anything from the schedule he has written.
You are given a int[] minuteValues representing minute parts of the times as written by Waving.
An hour assignment can be represented by a int[] whose i-th element is the hour part
corresponding to minuteValues[i]. The assignment is considered valid if and only if
the schedule obtained from the assignment follows the rules mentioned above. Help Waving by
returning the K-th (1-indexed) lexicographically smallest valid hour assignment. If there are
less than K valid hour assignments, return a int[] containing single element -1 instead.
|
| |
Definition |
| | | Class: | WeirdTimes | | Method: | hourValues | | Parameters: | int[], int | | Returns: | int[] | | Method signature: | int[] hourValues(int[] minuteValues, int K) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | int[] X is lexicographically smaller than int[] Y of the same size iff there exists an index i such that X[j] = Y[j], j < i, and X[i] < Y[i]. |
| |
Constraints |
| - | minuteValues will contain between 1 and 50 elements, inclusive. |
| - | Each element of minuteValues will be between 0 and 59, inclusive. |
| - | K will be between 1 and 1,000,000,000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: {0, 1, 3 } | The three lexicographically smallest valid hour assignments and the corresponding schedules obtained from them are:
{0, 1, 1} ---> {00:22, 01:11, 01:33}
{0, 1, 2} ---> {00:22, 01:11, 02:33}
{0, 1, 3} ---> {00:22, 01:11, 03:33}
|
|
|
| 1) | |
| | | Returns: {1 } | All possible schedules in lexicographically sorted order are
00:10, 01:10, 02:10, 03:10, 04:10, 05:10, 06:10, 07:10,
08:10, 09:10, 10:10, 11:10, 12:10, 13:10, 14:10, 15:10,
16:10, 17:10, 18:10, 19:10, 20:10, 21:10, 22:10, 23:10.
|
|
|
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} | 1 |
| Returns: {-1 } | | In the list of minute parts, each next element is less than or equal to the previous one. Operations must follow in chronological order and no two operations can be performed at the same time, so no two listed operations can happen within the same hour. There are 25 elements in the list, but a single day consists of just 24 hours, therefore there are no valid hour assignments. |
|
|
| 5) | |
| | {45, 12, 0, 3, 2, 7, 4, 9, 23, 6, 17, 33} | 12345 |
| Returns: {0, 1, 2, 2, 3, 3, 4, 5, 12, 13, 18, 18 } | |
|
| 6) | |
| | |