This is similar to a problem I encountered a couple of years ago: mixing liquids to avoid stratification. The idea is that if you’re mixing liquids A, B, and C into a container, you don’t want to just pour them into the container one after the other. Rather, you want to add some A, some B, some C, etc., in the relative proportions.
It’s the same problem as evenly distributing items in a list.
Say you have 30 of type A, 20 of type B, and 10 of type C, for a total of 60 videos. Every other video, then, has to be an A. Every third video is a B, and every sixth video is a C.
So the A’s are at 0,2,4,6,8,etc. B’s are at 0,3,6,9,12,etc. And the C’s are at 0,6,12,18,etc.
Obviously, you have collisions that you must resolve.
The way I did this is to build a min heap that contains the video type and its frequency, and its current position, which starts at frequency/2. So the heap contains: {A,2,1},{B,3,1},{C,6,3}.
To generate your list, remove the lowest item from the heap and add it to your list. Then, add its frequency to the current position, and put it back on the heap. So after the first time through, you’ve output the A, and your heap now contains: {B,3,1},{A,2,2},{C,6,3}.
Output the B, and then add it back, giving you {A,2,2},{C,6,3},{B,3,4}
You’ll of course also want to keep a count of each item, which you decrement each time that item is output, and you don’t add it back to the heap if the count goes to 0.
I wrote about this at some length in my blog about a year ago. See Evenly distributing items in a list.
As far as efficiency is concerned, the algorithm has complexity O(n log k), where n is the total number of videos, and k is the number of video types.