Как выбрать подборку строк с минимальной разницей в дате

Question

Вопрос было сложно сформулировать.Надеюсь, это будет иметь смысл.

У меня есть таблица предметов в моем инвентаре.

Давайте назовем предметы Apple, Orange, Pear, Potato.Я хочу выбрать корзину ФРУКТОВ (1 x яблоко, 1 x апельсин, 1 x груша).

У каждого предмета в ИНВЕНТАРЕ есть своя дата доступности.Так что ...

1. Яблоко ЯНВАРЬ
2. Яблоко ФЕВРАЛЬ
3. Яблоко МАРТ
4. Оранжевый АПРЕЛЬ
5. Яблоко АПРЕЛЬ
6. Груша МАЙ

Я не хочу выбирать предметы в порядке их появления в инвентаре,Вместо этого я хочу выбрать их в соответствии с минимальным диапазоном дат, в который можно выбрать все элементы.то есть Orange & Apple в АПРЕЛЕ и груша в мае.

Я не уверен, является ли это проблемой для MYSQL или для некоторых массивов PHP.Я в тупике.Заранее спасибо.

Answer 1

Если массив фруктов еще не отсортирован по дате, давайте его отсортируем.

Теперь простое решение O (n ^ 2) будет проверять все возможные диапазоны.Псевдокод без языка:

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

Вы можете найти, что он достаточно хорош.
Или вы можете написать более сложное решение O (n).Это просто раздвижное окно [first, last].На каждом шаге мы перемещаем либо левую границу (исключая один фрукт из корзины), либо правую (добавляя один фрукт в корзину).

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 2

Звук довольно сложный.Для решения этой проблемы я могу сгруппировать каждый фрукт в группу месяцев доступности и посмотреть, сколько их в каждой группе.

1. ЯНВАРЬ (1)
2. ФЕВРАЛЬ (1)
3. МАРТ (1)
4. АПРЕЛЬ (2)
5. МОЖЕТ (1)

Чтобы увидеть, что большинство фруктов приходится на АПРЕЛЬ.Таким образом, АПРЕЛЬ является нашим предпочтительным месяцем.

Я бы тогда удалил элементы из месяцев с дубликатами (яблоки в вашем примере), что убрало бы МАРТ в качестве опции.Этот шаг может быть выполнен либо сейчас, либо после следующего шага, в зависимости от ваших данных и полученных вами результатов.

Затем я посмотрю на следующий самый популярный месяц и посчитаю, как далеко этот месяц находится (например,Январь 3 апреля от апреля, 1 марта и т. Д.).Если у вас был галстук, то не важно, какой вы выберете.В этом примере вы, в конечном счете, выбрали бы 2 фрукта от АПРЕЛЯ и 1 фрукт от МАЯ по вашему запросу.

Этот подход может не сработать, если самый популярный месяц фактически не приводит к «лучшему» выбору.

Answer 3

Приведенная вами таблица инвентаризации структурирована:

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";