Problem Statement |
| |
You have n distinct songs in your music player, numbered 1 through n. Some of these songs are good and the rest are bad. The good songs are given in the int[] best.
Your task is to order your songs into a playlist where each song appears exactly once. The goal is to maximize the total number of times you hear a good song in shuffle mode. In shuffle mode, your music player plays the a[0]-th song in your playlist, followed by the a[1]-th song, etc. All indices are 1-based. If the same song is played multiple times, each time counts toward the total.
Return a int[] containing the playlist that will achieve this goal. If there are multiple possible return values, choose the one that comes earliest lexicographically. A int[] a comes before a int[] b if a contains a smaller element at the first index where they differ.
|
| |
Definition |
| | | Class: | Playlist | | Method: | trackSort | | Parameters: | int, int[], int[] | | Returns: | int[] | | Method signature: | int[] trackSort(int n, int[] best, int[] a) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | n will be between 1 and 50, inclusive. |
| - | best will contain between 0 and n elements, inclusive. |
| - | All elements of best will be distinct. |
| - | a will contain between 0 and 50 elements, inclusive. |
| - | Each element of best and a will be between 1 and n, inclusive. |
| |
Examples |
| 0) | |
| | 3 | {1, 2} | {3, 2, 3, 3, 1, 2} |
| Returns: {3, 1, 2 } | | There are 3 songs, and songs 1 and 2 are good. If you order the tracks in your playlist {3, 1, 2} or {3, 2, 1}, you will hear a good song 5 times in shuffle mode. In case of a tie, you should choose the one that comes earliest lexicographically, so the answer is {3, 1, 2}. |
|
|
| 1) | |
| | | Returns: {1, 2, 3, 4, 5 } | | In this case, there are no good songs, so you should just choose the playlist that comes first lexicographically: {1, 2, 3, 4, 5}. |
|
|
| 2) | |
| | 6 | {3, 5} | {1, 2, 3, 4, 5, 2, 3, 2, 6} |
| Returns: {1, 3, 5, 2, 4, 6 } | |
|
| 3) | |
| | 3 | {3, 2, 1} | {3, 1, 2, 3, 2, 1, 2, 1, 3} |
| Returns: {1, 2, 3 } | |
|
| 4) | |
| | 5 | {4, 5, 3} | {5, 5, 5, 3, 2, 1, 4, 3} |
| Returns: {1, 2, 3, 4, 5 } | |
|
| 5) | |
| | 10 | {8, 5, 1, 7} | {6, 6, 4, 4} |
| Returns: {1, 2, 3, 5, 4, 7, 6, 8, 9, 10 } | |
|
| 6) | |
| | 8 | {6} | {2, 8, 3, 1, 5, 7, 7, 8, 4, 4} |
| Returns: {1, 2, 3, 4, 5, 7, 6, 8 } | |
|