Vzhľadom na ľubovoľnú sériu vstupných údajov s jednýmstav buď Otvorený alebo Zatvorený tak, že existuje minimálne jeden vstupný dátum (otvorený stav), ktorý vedie k tomu, že sa pridá jeden dátum (Uzavretý, max. dátum) na dokončenie výstupnej postupnosti, aký algoritmus by ste použili na vygenerovanie výstupu, ktorý poslúcha nasledujúce?
1. Neexistujú žiadne po sebe idúce dátumy otvorenia a žiadne po sebe idúce dátumy zatvorenia.
2. Pre každý dátum otvorenia existuje presne jeden dátum zatvorenia.
3. Prvý dátum by mal byť otvorený a posledný dátum by mal byť uzavretý.
4. Okrem prvého dátumu otvorenia a posledného dátumu zatvorenia by mal každý dátum otvorenia bezprostredne nasledovať po predchádzajúcom dátume zatvorenia, alebo inak, každý dátum zatvorenia by mal byť deň pred nasledujúcim dátumom otvorenia.
5. Konečný dátum je uzavretý a maximálny dátum (9999-12-31, v tomto príklade)
Toto nie je domáce cvičenie, som implementovaltoto je v C # a je to výrobný kód, ktorý sa spustí miliónkrát. Výkon je dôležitý, áno, ale do značnej miery sekundárny kvôli čitateľnosti. Algoritmus, ktorý som použil, funguje úplne dobre, ale vyzerá hrozne. Akýkoľvek jazyk vítaný. Prekladám podľa potreby. Vďaka.
Príklad 1
input:
[2000-01-01,open]
output:
[2000-01-01,open]
[9999-12-31,closed]
Príklad 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]
Príklad 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]
Príklad 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]
Odvažujem sa opýtať, ktorá trieda jazyka rieši tento druh problému najlepšie?
odpovede:
5 pre odpoveď č. 1- Zoraďte vstup podľa dátumu.
- Iterujte vstupom a sledujte aktuálny stav.
- Ak je stav otvorený a zistí sa dátum otvorenia, zadajte dátum zatvorenia.
- Ak je stav zatvorený a vyskytne sa dátum uzavretia, zadajte dátum otvorenia.
- Ak je stav uzavretý a zistí sa dátum otvorenia, ktorý nie je dňom nasledujúcim po predchádzajúcom dátume uzavretia, vyplňte medzeru dátumom otvorenia a dátumom uzavretia.
- Po dokončení opakovania pomocou vstupu, ak je stav otvorený, zadajte konečný dátum uzavretia.
- Po dokončení iterácie vstupom, ak je stav uzavretý a konečný dátum uzavretia nie je 9999-12-31. vložte konečný dátum otvorenia a zatvorenia.
0 pre odpoveď č. 2
Najskôr môžete vygenerovať zoznam všetkých otvorených dátumov a potom vypočítať konečné dátumy odpočítaním jedného dňa od každého okrem prvého dátumu otvorenia:
Pseudokód 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 pre odpoveď č. 3
Takže riešenie by malo byť rýchle od výkonuje tu rozhodujúce. Tiež by mal podporovať online spracovanie, takže keď je systém spustený, môžete kedykoľvek pridať nové dátumy otvorenia / zatvorenia a okamžite získať aktualizovaný rozvrh.
Hlavnou činnosťou tohto problému jetriedenie, navrhol by som použiť hromadu. Každý uzol v halde ukladá dvojicu dátum / stav. Algoritmus začína prázdnou hromadou a neustále ju vyvíja ako čítanie vstupov. Keď prichádzajú nové údaje, algoritmus ich vloží do stromu, ktorý vezme O (lgN). Keď dôjde k požiadavke na vytiahnutie rozvrhu, algoritmus vykoná posuv v poradí, ktorý preberie O (N). Algoritmus by sa mal tiež raz za čas vyvážiť, aby sa dosiahol lepší výkon.