There are three ads: A, B, and C. Ad A has paid for 60M impressions, B 30M impressions, and C 10M impressions. All ads are scheduled to run during the same time period. Try to show all ads as fairly as possible.
One approach would be to show all A first, then all of B next, then C. This however means B can’t be shown until all of A are finished, and C can’t be shown until all of B are finished.
A better distribution is to randomize the selection and each ad should be selected some percent of the whole, in this case 60% for A, 30% for B, and 10% for C. Allocate an array of 10 elements, the first 6 elements contain A, the next 3 contain B, and the last 1 contains C. A random selection between 0 and 9 from the array determines which ad to serve next. Here is pseudocode:
id adIds = [a,a,a,a,a,a,b,b,b,c]
id getNextAd(adIds) {
adIndex = random() % adIds.length
adToShow = adIds[adIndex]
return adToShow
}
This yields a nice weighted random distribution for ads scheduled to run during the same time period. Searching for the next ad to show is O(1) time.