Shortest Balanced Playlist Segment
At Spotify, we're constantly striving to enhance the listening experience through intelligent playlist curation. A key aspect of a high-quality playlist is its 'balance' — ensuring a diverse selection of music while keeping segments concise and focused. For our automated playlist generation system, we need to identify optimal sub-segments that meet specific criteria.
This problem challenges you to find the shortest continuous segment within a given playlist that satisfies both a minimum genre diversity and a maximum total duration constraint. This helps in creating 'mini-mixes' or dynamic transitions within larger playlists.
Your task is to implement a function shortestBalancedPlaylistSegment that takes a playlist (an array of Track objects), a minimum number of distinct genres, and a maximum total duration. The function should return the length of the shortest contiguous sub-segment of tracks that meets both of the following conditions:
minDistinctGenres unique genres.duration of tracks within the sub-segment is at most maxTotalDuration.If no such sub-segment exists in the playlist, return -1.
Input:
tracks: An array of Track objects. Each Track object has two properties:
genre: A string representing the music genre (e.g., "pop", "rock", "jazz").duration: A number representing the track's duration in seconds.minDistinctGenres: A number representing the minimum required count of distinct genres in the segment.maxTotalDuration: A number representing the maximum allowed total duration of the segment.Output:
tracks array will not be provided as input (see constraints).minDistinctGenres is 1, any single track itself (if its duration is within maxTotalDuration) forms a valid segment of length 1.Examples
Example 1
Input:
tracks = [{"genre": "pop", "duration": 10}, {"genre": "rock", "duration": 5}, {"genre": "pop", "duration": 8}, {"genre": "jazz", "duration": 12}], minDistinctGenres = 2, maxTotalDuration = 20
Output:
2
Note:
The segment [{ genre: "rock", duration: 5 }, { genre: "pop", duration: 8 }] has 2 distinct genres ("rock", "pop") and total duration 13 <= 20. Its length is 2. The segment [{ genre: "pop", duration: 8 }, { genre: "jazz", duration: 12 }] also has 2 distinct genres ("pop", "jazz") and total duration 20 <= 20. Its length is 2. This is the shortest possible.
Example 2
Input:
tracks = [{"genre": "pop", "duration": 100}, {"genre": "rock", "duration": 100}], minDistinctGenres = 2, maxTotalDuration = 50
Output:
-1
Note:
Any segment containing 2 distinct genres (e.g., the whole playlist) would have a total duration of 200, which exceeds maxTotalDuration = 50. No single genre segment satisfies minDistinctGenres = 2. Thus, no valid segment exists.
Example 3
Input:
tracks = [{"genre": "A", "duration": 1}, {"genre": "B", "duration": 1}, {"genre": "C", "duration": 1}, {"genre": "A", "duration": 10}, {"genre": "D", "duration": 1}], minDistinctGenres = 3, maxTotalDuration = 5
Output:
3
Note:
The segment [{ genre: "A", duration: 1 }, { genre: "B", duration: 1 }, { genre: "C", duration: 1 }] has 3 distinct genres and total duration 3 <= 5. Its length is 3. Other segments like [{ genre: "B", duration: 1 }, { genre: "C", duration: 1 }, { genre: "A", duration: 10 }] have 3 distinct genres but duration 12 > 5. No shorter segment satisfies both conditions.
Constraints
1 <= tracks.length <= 10^5track.genre is a string with length between 1 and 20, consisting of lowercase English letters.track.duration is an integer between 1 and 10^9.1 <= minDistinctGenres <= tracks.length1 <= maxTotalDuration <= 10^14 (The sum of durations can be large, but fits within standard 64-bit floating-point numbers used by JavaScript's number type without precision loss for integers up to 2^53 - 1).Loading editor...