I have a list of webpages and I must download them frequently, each webpage got a different download frequency. Based on this frequency we group the webpages in 5 groups:
Items in group 1 are downloaded once per 1 hour items in group 2 once per 2 hours items in group 3 once per 3 hours items in group 4 once per 12 hours items in group 5 once per 24 hours
This means, we must download all the group 1 webpages in 1 hour, all the group 2 in 2 hours etc.
I am trying to make an algorithm. As input, I have:
DATA_ARR = one array with 5 numbers. Each number represents the number of items in this group.
TIME_ARR = one array with 5 numbers (1, 2, 3, 12, 24) representing how often the items will be downloaded.
X = the total number of webpages to download per hour. This is calculated using items_in_group/download_frequently and rounded upwards.
If we have 15 items in group 5, and 3 items in group 4, this will be 15/24 + 3/12 = 0.875 and rounded is 1.
Every hour my program must download at max
X sites. I expect the algorithm to output something like:
Hour 1: A1 B0 C4 D5 Hour 2: A2 B1 C2 D2 ...
A1 = 2nd item of 1st group
C0 = 1st item of 3rd group
My algorithm must be as efficient as possible. This means that I should never download items more often than the update frequency of their group (unless I have absolutely no other choice)(see example)
group 1: 0 items | once per 1 hour group 2: 3 items | once per 2 hours group 3: 4 items | once per 3 hours group 4: 0 items | once per 12 hours group 5: 0 items | once per 24 hours
We calculate the number of items we can take per hour:
3/2+4/3 = 2.83. We round this upwards and it's 3.
Using pencil and paper, we can found the following solution:
Hour 1: B0 C0 B1 Hour 2: C1 B2 C2 Hour 3: B0 C3 B1 Hour 4: C0 B2 C2 Hour 5: B0 C1 B1 Hour 6: C3 B2 C2 and repeat the above.
C3 once every 3 hours. We also take
B2 once every 2 hours.
C2 once every 2 hours. This is more often than needed, wasting bandwidth, but if there is no other way around (like here), we will take it every 2 hours. My question on SO here and Math Overflow here made me understand that sometimes you are forced to download items more often than the absolutely minimum.
Question: Please, explain to me, how to design an algorithm able to download the items, while using the absolute minimum number of downloads? Brute force is NOT a solution and the algorithm must be efficient CPU wise because the number of elements can be huge.