алгоритм вставки даты

Question

У меня есть список, в нем есть объекты Foo, и у каждого Foo есть дата начала и дата окончания. Я хочу вставить новый объект Foo, который имеет собственную дату начала и окончания.

Я хочу, чтобы элементы в списке обновляли свои даты начала и окончания соответственно, когда новый объект Foo вставлен, и чтобы новый объект Foo нашел свое правильное место в списке. Я подожду и посмотрю, достаточно ли информации для того, чтобы кто-то понял мою проблему, и посмотрю, нужно ли мне объяснять дальше.

Answer 1

Чтобы найти точку вставки, вы можете использовать интерполяционный поиск (например, обрабатывать каждую дату целым числом в мсек), и когда элемент вставляется, он может запустить метод, который обновляет соседей, обновлять своих соседей при получении запроса на обновление, по линии.

Возможно, я слишком упрощаю вашу проблему, но из того, что я понимаю о вашем посте, это в среднем должно занять чуть больше O (n) времени.

Answer 2

Ваш новый объект Foo должен пройти по списку и найти, куда его нужно вставить. Но будьте осторожны, так как есть множество крайних случаев, которые могут испортить ваш список. Ваша логика должна работать в следующих ситуациях:

   1) The new interval fits into an existing interval -- do nothing
   2) The new interval begins and ends before the first interval -- 
           insert it at the front of the list
   3) The new interval stretches the existing start, end, 
      or both without cutting across adjacent intervals --
          replace the start or end date on existing Foo.
   4) The new interval begins after the end of the previous interval, but 
      ends after the beginning of the next interval --
           walk the list with a sentinel until you find a Foo that begins before
           the end of your new Foo. Delete the Foos that fall in 
           between the current Foo and the sentinel, adjusting the 
           end time if necessary.
   5) The new interval begins after the end of the last interval --
           insert it at the end of the list.

Возможно, мне не хватает граничного случая, но это модель, которую я использовал, когда мне пришлось решать очень похожую проблему.