How do I pick a selection of rows with the minimum date difference.

Question

Hi,

The question was difficult to phrase. Hopefully this will make sense.

I have a table of items in my INVENTORY.

Let's call the items Apple, Orange, Pear, Potato. I want to pick a basket of FRUIT (1 x Apple,1 x Orange, 1 x Pear).

Each item in the INVENTORY has a different date for availability. So that...

1. Apple JANUARY
2. Apple FEBRUARY
3. Apple MARCH
4. Orange APRIL
5. Apple APRIL
6. Pear MAY

I don't want to pick the items in the order they appear in the inventory. Instead I want to pick them according to the minimum date range in which all items can be picked. ie Orange & Apple in APRIL and the pear in MAY.

I'm not sure if this is a problem for MYSQL or for some PHP arrays. I'm stumped. Thanks in advance.

Answer 1

Given you table inventory is structured:

fruit, availability
apple, 3 // apples in march

//user picks the availability month maybe?
$this_month = 5 ;

//or generate it for today
$this_month = date('n') ;

// sql

"select distinct fruit from inventory where availability = $this_month";

Answer 2

If array of fruits isn't already sorted by date, let's sort it.

Now, the simple O(n^2) solution would be to check all possible ranges. Pseudo-code in no particular language:

for (int i = 0; i < inventory.length; ++i)
    hash basket = {}
    for (int j = i; j < inventory.length; ++j) {
        basket.add(inventory[j]);
        if (basket.size == 3) { // or whatever's the number of fruits
            // found all fruits
            // compare range [i, j] with the best range
            // update best range, if necessary
            break;
        }
    }
end

You may find it's good enough.
Or you could write a bit more complicated O(n) solution. It's just a sliding window [first, last]. On each step, we move either left border (excluding one fruit from the basket) or right (adding one fruit to the basket).

int first = 0;
int last = 0;
hash count = {};
count[inventory[0]] = 1;

while (true) {
    if (count[inventory[first]] > 0) {
        --count[inventory[first]];
        ++first;
    } else if (last < inventory.length) {
        ++last;
        ++count[inventory[last]];
    } else {
        break;
    }

    if (date[last] - date[first] < min_range
            && count.number_of_nonzero_elements == 3) {
        // found new best answer
        min_range = date[last] - date[first]
    }
}

Answer 3

Sound quite complicated. The way that I would approach the problem is to group each fruit into its availability month group and see how many are in each group.

1. JANUARY (1)
2. FEBRUARY (1)
3. MARCH (1)
4. APRIL (2)
5. MAY (1)

To see that the most fruits fall within APRIL. So APRIL is therefore our preferred month.

I would then remove the items from months with duplicates (Apples in your example), which would remove MARCH as an option. This step could either be done now, or after the next step depending on your data and the results you get.

I would then look at the next most popular month and calculate how far away that month is (eg. JAN is 3 away from APRIL, MARCH is 1 etc). If you then had a tie then it shouldn't matter which you choose. In this example though you would end up choosing the 2 fruits from APRIL and 1 fruit from MAY as you requested.

This approach may not work if the most popular month doesn't actually result in the "best" selection.