Design an in-memory playlist that combines song portions received from a DJ service and a recommendation service.

A song portion specifies the part of a song that must be played. For example, a portion starting at 90 seconds and ending at 220 seconds plays the song from 1:30 until 3:40.

The playlist may use equal or custom proportions of song portions from the two services. User-preference filters may also be applied.

Class

MusicPlaylist

Constructor

MusicPlaylist

MusicPlaylist( String mixType, int djWeight, int recommendationWeight, List<String> preferredTags)

• mixType is either "EQUAL" or "CUSTOM".
• For "EQUAL", both source weights must be 1.
• For "CUSTOM", the weights define the relative number of song portions selected from the two services.
• preferredTags contains every tag that a song portion must have to be eligible.
• An empty preferredTags list disables preference filtering.

Methods

addDjSong

void addDjSong( String songId, int startSecond, int endSecond, List<String> tags)

• Adds a playable portion of songId received from the DJ service.
• startSecond is the inclusive starting position.
• endSecond is the exclusive ending position.
• The duration of the added portion is endSecond - startSecond seconds.
• tags contains the tags associated with the song.

addRecommendedSong

void addRecommendedSong( String songId, int startSecond, int endSecond, List<String> tags)

• Adds a playable portion of songId received from the recommendation service.
• startSecond is the inclusive starting position.
• endSecond is the exclusive ending position.
• The duration of the added portion is endSecond - startSecond seconds.
• tags contains the tags associated with the song.

getPlaylist

List<String> getPlaylist(int maximumSongPortions)

• Returns at most maximumSongPortions eligible song portions in playback order.
• Every returned string has the format "source,songId,startSecond,endSecond".
• source is either "DJ" or "RECOMMENDATION".
• Returns all eligible portions when fewer than maximumSongPortions are available.
• Returns an empty list when no portion is eligible.

Rules

• The interval of a song portion is [startSecond, endSecond).
• To add an entire song, use 0 as startSecond and the song's complete duration as endSecond.
• Different portions of the same song may be added separately.
• Song portions from each service retain the order in which they were added.
• A song portion is eligible when its tags contain every value in preferredTags.
• Tag comparisons are case-sensitive.
• The mixing proportion is based on the number of song portions, not their individual durations.
• Let djPortionsUsed and recommendationPortionsUsed be the numbers of portions already selected from the respective services.
• When both services have eligible portions, select the next DJ portion if djPortionsUsed * recommendationWeight <= recommendationPortionsUsed * djWeight . Otherwise, select the next recommendation portion.
• When both sides of the comparison are equal, select the DJ portion.
• If one service runs out of eligible portions, continue with portions from the other service.
• Calling getPlaylist does not remove or modify stored portions.
• The returned values are playback instructions. The implementation does not modify or combine audio files.

Constraints

• mixType is "EQUAL" or "CUSTOM".
• 1 <= djWeight <= 100
• 1 <= recommendationWeight <= 100
• For "EQUAL", djWeight == recommendationWeight == 1.
• At most 100,000 song portions are added across both services.
• 1 <= songId.length() <= 100
• 0 <= startSecond < endSecond <= 86,400
• endSecond does not exceed the complete duration of the song.
• Every combination of source, song ID, start second, and end second is unique.
• 0 <= tags.size() <= 20
• 0 <= preferredTags.size() <= 20
• 1 <= tags.get(i).length() <= 50
• 1 <= preferredTags.get(i).length() <= 50
• Tags within the same list are unique.
• Song IDs and tags do not contain the comma character.
• 1 <= maximumSongPortions <= 100,000
• No parameter, input list, or list element is null.

Expected Efficiency

• Adding a portion should take time proportional to its number of tags.
• Let n be the number of stored portions, p the number of preferred tags, and k the number of returned portions.
• getPlaylist should run in O(n * (p + 1) + k) time.
• The playlist should use O(n) additional space.

Example 1

MusicPlaylist( mixType = "EQUAL", djWeight = 1, recommendationWeight = 1, preferredTags = List.of("rock"))

Output: a new empty playlist.

addDjSong( songId = "song-4", startSecond = 90, endSecond = 220, tags = List.of("rock", "dance"))

Output: no value.

addDjSong( songId = "song-9", startSecond = 15, endSecond = 75, tags = List.of("rock"))

Output: no value.

addRecommendedSong( songId = "song-12", startSecond = 30, endSecond = 150, tags = List.of("rock", "chill"))

Output: no value.

addRecommendedSong( songId = "song-15", startSecond = 45, endSecond = 105, tags = List.of("rock"))

Output: no value.

getPlaylist(maximumSongPortions = 4)

Output: List.of( "DJ,song-4,90,220", "RECOMMENDATION,song-12,30,150", "DJ,song-9,15,75", "RECOMMENDATION,song-15,45,105")

The first instruction plays song-4 from 1:30 until 3:40. Eligible portions from the two services are then alternated equally.

Example 2

MusicPlaylist( mixType = "CUSTOM", djWeight = 2, recommendationWeight = 1, preferredTags = List.of())

Output: a new empty playlist.

addDjSong( songId = "track-A", startSecond = 0, endSecond = 50, tags = List.of("dance"))

Output: no value.

addDjSong( songId = "track-B", startSecond = 80, endSecond = 160, tags = List.of("pop"))

Output: no value.

addDjSong( songId = "track-C", startSecond = 20, endSecond = 100, tags = List.of("rock"))

Output: no value.

addDjSong( songId = "track-D", startSecond = 120, endSecond = 210, tags = List.of("electronic"))

Output: no value.

addRecommendedSong( songId = "track-X", startSecond = 10, endSecond = 70, tags = List.of("acoustic"))

Output: no value.

addRecommendedSong( songId = "track-Y", startSecond = 40, endSecond = 130, tags = List.of("jazz"))

Output: no value.

getPlaylist(maximumSongPortions = 6)

Output: List.of( "DJ,track-A,0,50", "RECOMMENDATION,track-X,10,70", "DJ,track-B,80,160", "DJ,track-C,20,100", "RECOMMENDATION,track-Y,40,130", "DJ,track-D,120,210")

The output follows the custom DJ-to-recommendation proportion of 2:1, while every entry retains its requested playback interval.