Over the years you have collected a great mass of music from various artists. These days you have very little time to listen to your whole collection. You decide to make a single compilation that contains the best hits from each artist. Your first attempt at the compilation was to place the best hits in a random order. However, this resulted in songs from the same artist being close or even next to each other. This is highly undesirable since you hate listening to the same artist over and over again.
After some further consideration you realize that there must be some kind of an ultimate order - i.e., an order where artists are 'spread out' across the compilation as much as possible. You then come up with a distance metric (D) that measures the 'spread' of artists across the compilation:
D(compilation) = Sum of all D(i), where D(i) is the distance of the song at position i.
D(i) = k-i, where k is the smallest integer greater than i, such that the songs at positions k and i are by the same artist. 0 if no such k exists.
Each element in artists will be formatted as "<artist name> <number of hits>". Your task is to make a String[] compilation of these artists such that D(compilation) is maximal. If there is more than one such compilation return the one which is lexicographically earliest. |