Curated Playlist Selection
Spotify is all about discovering new music. To help users find high-quality, popular tracks that align with specific listening habits, we often curate playlists dynamically. This problem focuses on the algorithmic core of selecting tracks for such a playlist, combining filtering, top-K selection, and multi-criteria sorting.
You are tasked with implementing a function getCuratedPlaylist that takes a list of Track objects, a minPlays threshold, a maxPlays threshold, and an integer k. The function should return a list of Track objects that satisfy the following criteria:
playCount is greater than or equal to minPlays AND less than or equal to maxPlays.k tracks with the highest playCount. If there are fewer than k tracks after filtering, return all of them. If multiple tracks have the same playCount and are vying for the k-th spot, any of them can be chosen.k selected tracks alphabetically by their title. If two tracks have the same title, sort them alphabetically by their artist.The function signature is getCuratedPlaylist(tracks: Track[], minPlays: number, maxPlays: number, k: number): Track[].
tracks: An array of Track objects. Each Track object has the following structure:
interface Track {
id: string;
title: string;
artist: string;
genre: string;
playCount: number;
}
id: A unique string identifier for the track.title: The title of the track (string).artist: The artist of the track (string).genre: The genre of the track (string).playCount: The total play count for the track (number).minPlays: A non-negative integer representing the minimum inclusive play count for a track to be considered.
maxPlays: A non-negative integer representing the maximum inclusive play count for a track to be considered.
k: A positive integer representing the maximum number of tracks to include in the curated playlist.
Returns: An array of Track objects, sorted as specified.
tracks input: If the tracks array is empty, the function should return an empty array.k value: If k is 0, an empty array should be returned. If k is larger than the number of tracks satisfying the filter and popularity criteria, return all available tracks.minPlays / maxPlays: Assume minPlays <= maxPlays.id is unique, but title and artist pairs might not be globally unique (though unlikely in practice, assume for sorting purposes).Examples
Example 1
Input:
tracks = [{"id": "1", "title": "Song A", "artist": "Artist X", "genre": "Pop", "playCount": 100}, {"id": "2", "title": "Song B", "artist": "Artist Y", "genre": "Rock", "playCount": 150}, {"id": "3", "title": "Song C", "artist": "Artist X", "genre": "Pop", "playCount": 120}, {"id": "4", "title": "Song D", "artist": "Artist Z", "genre": "Jazz", "playCount": 90}], minPlays = 100, maxPlays = 200, k = 2
Output:
[{"id": "2", "title": "Song B", "artist": "Artist Y", "genre": "Rock", "playCount": 150}, {"id": "3", "title": "Song C", "artist": "Artist X", "genre": "Pop", "playCount": 120}]
Note:
Tracks with play counts between 100 and 200 are Song A (100), Song B (150), Song C (120). The top 2 by play count are Song B (150) and Song C (120). Sorted alphabetically by title, then artist: Song B, Song C.
Example 2
Input:
tracks = [{"id": "1", "title": "Track Alpha", "artist": "Artist A", "genre": "Pop", "playCount": 50}, {"id": "2", "title": "Track Beta", "artist": "Artist B", "genre": "Rock", "playCount": 200}], minPlays = 100, maxPlays = 300, k = 3
Output:
[{"id": "2", "title": "Track Beta", "artist": "Artist B", "genre": "Rock", "playCount": 200}]
Note:
Only 'Track Beta' (200 plays) falls within the [100, 300] range. Since k=3 and only one track is available, 'Track Beta' is returned.
Example 3
Input:
tracks = [{"id": "1", "title": "Great Hit", "artist": "Band A", "genre": "Pop", "playCount": 1000}, {"id": "2", "title": "Great Hit", "artist": "Band B", "genre": "Rock", "playCount": 1200}, {"id": "3", "title": "Fantastic Song", "artist": "Solo X", "genre": "Jazz", "playCount": 1100}], minPlays = 500, maxPlays = 1500, k = 3
Output:
[{"id": "3", "title": "Fantastic Song", "artist": "Solo X", "genre": "Jazz", "playCount": 1100}, {"id": "1", "title": "Great Hit", "artist": "Band A", "genre": "Pop", "playCount": 1000}, {"id": "2", "title": "Great Hit", "artist": "Band B", "genre": "Rock", "playCount": 1200}]
Note:
All three tracks are within the play count range. The top 3 by play count are all of them. When sorting, 'Fantastic Song' comes before 'Great Hit'. For 'Great Hit', 'Band A' comes before 'Band B'.
Constraints
0 <= tracks.length <= 10^5 (N)0 <= minPlays <= maxPlays <= 10^90 <= k <= 10^50 <= track.playCount <= 10^9track.id, track.title, track.artist, track.genre are non-empty strings.O(N log K) or O(N log N) for time, O(N) or O(K) for space).Loading editor...