Като се има предвид всяка серия от входни дати с единичнасъстоянието на Отворено или Затворено, така че при много малко има една дата на въвеждане (отворено състояние), което води до една дата (Затворена, макс. Дата) се добавя за завършване на изходната последователност кой алгоритъм бихте използвали за генериране на изход, се подчинява на следното?
1. Няма последователни дати на Отваряне и няма последователни Затворени дати.
2. За всяка Отворена дата има точно една Затворена дата.
3. Първата дата трябва да бъде Отваряна и последната дата трябва да бъде затворена.
4. Освен първата дата на Отваряне и последната Затворена дата, всяка Отворена дата трябва да следва непосредствено предишната Затворена дата или да бъде поставена по друг начин, всяка Затворена дата трябва да бъде деня преди следващата Отворена дата.
5. Крайната дата е Closed и Max date (9999-12-31, в този пример)
Това не е упражнение за домашна работа, внедрих сетова в C # и неговия производствен код, който ще се изпълнява милиони пъти.Произвеждането е важно, да, но много по-второстепенно от четливостта.Използваният алгоритъм работи перфектно, но изглежда ужасно. Всеки език е добре дошъл. Ще превеждам според нуждите. Благодаря.
Пример 1
input:
[2000-01-01,open]
output:
[2000-01-01,open]
[9999-12-31,closed]
Пример 2
input:
[2000-01-01,open]
[2001-01-01,open]
output:
[2000-01-01,open]
[2000-12-31,closed]
[2001-01-01,open]
[9999-12-31,closed]
Пример 3
input:
[2000-01-01,open]
[2004-04-30,closed]
output:
[2000-01-01,open]
[2004-04-30,closed]
[2004-05-01,open]
[9999-12-31,closed]
Пример 4
input:
[2000-01-01,open]
[2000-03-17,open]
[2002-09-11,closed]
[2003-04-07,closed]
output:
[2000-01-01,open]
[2000-03-16,closed]
[2000-03-17,open]
[2002-09-11,closed]
[2002-09-12,open]
[2003-04-07,closed]
[2003-04-08,open]
[9999-12-31,closed]
Смея да попитам кой клас език най-добре решава този проблем?
Отговори:
5 за отговор № 1- Сортирайте входа по дата.
- Повторете чрез входа, като следите текущото състояние.
- Ако състоянието е отворено и е открита открита дата, въведете затворена дата.
- Ако състоянието е затворено и е открита дата на приключване, въведете отворена дата.
- Ако състоянието е затворено и е открита открита дата, която не е ден след предишната дата на закриване, въведете отворена дата и дата на закриване, за да запълни тази празнина.
- Когато приключите с итерацията чрез вход, ако състоянието е отворено, въведете окончателно затворена дата.
- Когато се направи итерация чрез въвеждане, ако състоянието е затворено и окончателната дата на приключване не е 9999-12-31. въведете последните отворени и затворени дати.
0 за отговор № 2
Първо можете да генерирате списък с всички отворени дати и след това да изчислите датите на приключване, като извадите един ден от всяка от първите дни на откриване:
C # псевдо-код:
var opendates = input.Select ( date =>
date.Type == closing ? date.Date + 1day : date.Date
).Sort ();
closingdates = opendates.Skip (1).Select (date => date - 1).Append ( new Date [] { 9999-12-31 } );
0 за отговор № 3
Така че решението трябва да е бързо, тъй като изпълнениетое от решаващо значение тук. Също така трябва да поддържа онлайн обработка, така че когато системата работи, можете да добавите нови дати на откриване / закриване по всяко време и да получите актуализиран график веднага.
Като основна операция в този проблем есортиране, бих предложил да използвате купчина. Всеки възел в куп съхранява двойка дата / състояние. Алгоритъмът започва с празен куп и непрекъснато го развива като входове за четене. Когато се появи нова информация, алгоритъмът я вмъква в дървото, което отнема O (lgN). Когато има заявка за изваждане на график, алгоритъмът изпълнява траверса в порядъка, който отнема O (N). Алгоритъмът също трябва да се балансира веднъж за по-добра ефективност.