Выбор массива/диапазона

Question

Это было задано в интервью, и я не смог найти решение. Сценарий состоит в том, что существует массив весов (некоторых элементов). Стоимость выбора предмета: . Теперь, если вы выберете товар с весом w, вы получите все товары в диапазоне [w, w + 4] как бесплатно. Задача алгоритма заключается в достижении минимальной стоимости и выборе всех элементов.

Мой подход состоял в том, чтобы иметь максимальную кучу и перемещаться по массиву, и, пройдя по массиву, вычислите количество предметов, которые можно получить бесплатно, путем сбора текущего элемента и использования максимальной кучи для выбора предметов, которые обеспечивают максимальные значения для свободно. Интервьюер сказал ОК, но попросил меня о лучшем решении, так как сама обходящая часть стоит O (n^2).

Конкретный пример

Weights array: 1 2 3 17 10 
Minimum cost 3: I pick 1, get 2 and 3 for free and then pick both 17 and 10 

Answer 1

не уверен, что это правильное решение, но если отсортировать список/массив, который вы могли бы пройти свой список, чтобы найти самый большой подсписок в диапазоне [ш, ш + 4]. вычитайте это значение из размера вашего списка и минимальной стоимости.

это будет стоить вам O (NlogN), а самая дорогая операция будет сортировка

List<Integer> list = Arrays.asList(1 ,2, 3,2, 17, 10); 
    Collections.sort(list);//O(logN*N) 
    int a=0,b=0; 
    do { 
     if (list.get(b+1)-list.get(a)<4){ 
      b++; 
     }else{ 
      a++; 
      b++; 
     } 

    }while(b<list.size()-1); 
    int minCost = list.size()-(b-a); 
    System.out.println(minCost); 

Это просто пример, может быть лучшим решением