Music player that plays the most frequent unplayed song

Users keep arriving, each with a list of songs, and every song's count goes up each time it appears. The player must always play the most frequent song that has not been played yet; a played song can only come back once every song has been played. Design the structure that supports adding users and choosing the next song efficiently.