Playlist Partitioning
Learn this problem
TiktokOAProblem statement
The TikTok stores content creators' videos in a distributed database, where each videoCategory[i] represents the number of videos available in the ith content category. To improve the efficiency, the system needs to create some content playlists such that:
- Each playlist contains exactly
kdistinct content categories. - Each video can only belong to one playlist.
Determine the maximum number of playlists that can be created while following these rules.
Function
maxPlaylists(videoCategory: int[], k: int) → int
Complete the function maxPlaylists in the editor.
maxPlaylists has the following parameters:
int[] videoCategory: an array of integers representing the number of videos in each categoryint k: the number of distinct content categories each playlist must contain
Returns
int: the maximum number of playlists that can be created
Examples
Example 1
videoCategory = [1, 2, 2, 3]k = 3return = 2Each playlist must include 2 videos from different categories. There are 4 different categories. One of the optimal arrangements is as follows:
- Playlist 1 gets videos from categories 2, 3, and 4. Thus remaining videos for each category is: [1, 1, 1, 2].
- Playlist 2 contains videos from categories 1, 2 and 4. Thus remaining videos for each category is: [0, 0, 1, 1].
Note that for the second playlist we could have chosen any 3 categories and one video from each of them, not necessarily from categories 1, 2 and 4. For example: 1, 3 and 4 or 2, 3, and 4 could also have been chosen.
It can be shown that no more than 2 playlists can be created. Therefore, the answer is 2.