узнать больше о дате?

Question

У меня запланировано множество событий, и я хочу проверить, есть ли 10-дневный интервал в запланированных событиях, где в течение 10 дней не происходит никакого события. Есть ли хорошая структура данных и поиск, чтобы найти 10-дневный интервал?

Answer 1

Зависит ли вы от эффективности, использования памяти и т. Д. Если все остальное не удается, вы можете сортировать по дате с использованием алгоритма O (n * log (n)) и принимать разницу между каждой последовательной парой дат.

EDIT: Думаю, я понимаю вашу проблему лучше сейчас. Два варианта: 1) Предполагая, что даты отсортированы, бинарный поиск их останавливается, когда приращение между двумя из них равно < 10. Возможно, вы могли бы искать подмассивы с более крупными диапазонами дат. Это находится где-то между log n и n. 2) Хранить разницу с предыдущей или следующей датой с датами. Используйте очередь приоритетов, чтобы сортировать их по разнице с предыдущей или следующей датой. Вы можете поместить дату с максимальной разницей в постоянное время.

Answer 2

Я бы использовал упорядоченный связанный список для хранения событий, а также я бы сохранил события в хеш-таблице (key: event date), которые по крайней мере на 10 дней раньше, чем следующая. Когда вы вставляете новое событие в связанный список, вы должны проверить разницу дат между новым событием и его соседями. До этого измените хэш-таблицу.

EDIT:

Может быть, нет необходимости для создания дополнительного Hashtable. Создать специальный упорядоченный связанный список, где список-элемент выглядит так:

[EVENTDATE | nextEventPointer | next10DayEventPointer | previous10DayEventPointer]

next10DayEventPointer указывает на следующее событие, которое, по крайней мере на 10 дней раньше, чем на следующий один. previous10DayEventPointer указывает на предыдущее событие, которое по крайней мере на 10 дней раньше следующего.

Элемент HEAD next10DayEventPointer указывает на первое событие, которое, по крайней мере, раньше следующего. Элемент HEAD previous10DayEventPointer равен NULL.

Вы можете запросить начало событий 10Day в HEAD, используя next10DayEventPointer.

Во время ввода вам необходимо обновить указатели, если это необходимо.

EDIT:

Используйте бинарный поиск, как это:

class Program 
{ 
    static void Main(string[] args) 
    { 
     Dictionary<int, int> result = new Dictionary<int, int>(); 
     int [] dates = {2, 2, 2, 2, 2, 7,18, 19, 23, 33, 34, 35, 50, 70}; 

     IsThereIntervalXBetween(dates, 10, 0, dates.Length - 1, result); 
     foreach (var key in result.Keys) 
      Console.WriteLine("Index:{0} Date:{1} Next:{2}",key,dates[key],dates[key+1]); 
    } 

    static void IsThereIntervalXBetween(int[] dates, int interval, int firstIndex, int lastIndex, Dictionary<int, int> result) 
    { 
     if (lastIndex - firstIndex == 1) 
     { 
      result.Add(firstIndex, dates[firstIndex]); 
      return; 
     } 

     int middleIndex = (firstIndex + lastIndex)/2; 

     if (dates[middleIndex] - dates[firstIndex] >= interval) 
      IsThereIntervalXBetween(dates, interval, firstIndex, middleIndex, result); 


     if (dates[lastIndex] - dates[middleIndex] >= interval) 
      IsThereIntervalXBetween(dates, interval, middleIndex, lastIndex, result); 
    } 
} 

Это рекурсивная, что не является предпочтительным, но все это легко превратить в нерекурсивна.

Answer 3

Вы можете отсортировать связанный список, чтобы сохранить расписание, а также сохранить его на карте хэша с указанием даты в качестве ключа и значения в качестве адреса узла-адреса связанного списка. Поэтому для поиска и просмотра, есть ли у вас 10 дней для расписания, время o (1) и вставить расписание в максимальное время (n).