Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ну да, это если для одного
PD>Если для нескольких — WHERE условие AND id IN [...] Но тут уже надо определить, в чем условие заключается и написать его корректно, а то можно вместо O(logN) получить O(N)


PD>Зачем его сортировать ? На это TreeSet есть, сразу его и строить, он SortedSet
Ну, так тоже можно. На самом деле всё чуть сложнее, т.к. события — это не точки, а интервалы. И надо строить алгебру интервалов. Но, вроде бы, там непринципиальное изменение сложности.

PD>Тогда в SQL совсем просто : SELECT where timestamp> table.timestamp AND id = ... TOP 1.
PD>При индексе по DateTime будет именно то, что надо
Ну, если хочется поговорить об индексах, то индекс по timestamp тут не поможет. Нужен будет индекс по (id, timestamp).

PD>>>Просто их все удалить и новые добавить.
S>>Непонятно, в какой момент добавлять новые.

PD>Трансакцией "удаление — добавление", если БД.
Вопрос был не "при помощи чего", а "в какой момент".
Вот я взял и добавил в расписание рабочие дни на ближайшие 5 лет. Потом в какой то момент мне нужно пойти и добавить их ещё на следующие 5 лет.
Или, к примеру, если у нас появился новый государственный праздник, мне нужно догадаться удалить и перегенерировать рабочие дни от сейчас и до какой-то даты.

PD>Для миллиона расписаний будет немало, согласен. Но все равно их хранить надо. Ну и при O(logN) это все же лишь 20 операций.
Нет, не "всё равно". Для O(1) будет миллион строк, а не миллиард.

PD>>>Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным.
S>>Ну вот я бы всё же хотел получить реализацию с O(1) памяти, а не O(∞).
PD>Насчет O(1) я сомневаюсь, а вот O(LogN) пока получается.
Вопрос не в вычислительной сложнности, а в расходе памяти. Так что тут никакого O(LogN). Ну, и вычислительная сложность тут далеко не всегда потребует O(LogN).
Например банальное ежедневное событие, наступающее в 8:00, описывается O(1) функцией вида

TimeStamp GetNextOccurence(TimeStamp start, TimeZone zone) 
{
  var t = Date(start).AddHours(8);
  if (Time(start) > Time.FromHours(8))
    t = t.AddDays(1);
  return t;
}

PD>Ну БД тут только для того, чтобы проще было объяснить идею.
Тогда утверждение "БД сама сделает" нерелевантно.

PD>Впрочем, едва ли это понадобится. getNext вернет же не Set, а один элемент. Пересечение их всегда даст либо 0, либо 1 элемент. Объединение — от 1 до миллиона, верно, но тебе точно нужно объединить полученные от getNext DateTime для миллиона расписаний ? .
Для миллиона — нет. Но вместо того, чтобы сначала объединять множества, а потом выбирать из них наименьший элемент, больший заданного, можно просто вернуть Min(GetNext(s1), GetNext(s2)). Тогда комбинация двух O(1) расписаний останется O(1).