Dwa objawienia z ostatnich kilku dni ;-)
Chyba już wiem jaka jest fundamentalna różnica między firmami, które mają swoje HQ w USA, a tymi które mają w UE.
W tych w UE, szczególnie jeśli działają długo powstaje wśród pracowników takie przekonanie, że głównym celem istnienia firmy jest zatrudnianie ludzi i większość procesów istnieje tylko po to. W firmach amerykańskich nadal gdzieś się przebija do świadomości normalnych pracowników, że firma ma zarabiać pieniądze i tworzyć coś nowego.
Źródłem dumy w europejskich firmach jest to, że one działają zgodnie z procedurami, w amerykańskich to, że coś nowego powstało. Coś jakby taka rzecz, że w europejskich firmach przekonanie o sukcesie idzie z wnętrza, a w amerykańskich z zewnątrz.
Drugie olśnienie ;-) niby oczywiste, ale stała w algo jest jednak ważna ;-)
Robiłem zadanie z "Elements of Programming Interviews in Java: The Insiders' Guide", proste masz listę eventów jako tablicę tablic int[][] i każdy event to powiedzmy w liczbie minut od początku dnia start i stop eventu, i trzeba powiedzieć jaka będzie wysokość kalendarza (bo jak kilka eventów jest w tym samym czasie to się ustawią jeden pod drugim).
No i moje rozwiązanie jest takie, że sortuję wg. startu, a jak są takie same to wg końca (de facto to chyba mi nie jest nawet potrzebne) (przy okazji kolejne olśnienie ;-) które będzie dalej) i w końcu używam PriorityQueue z "końcami" eventów, usuwam je gdy nowy start jest wyższy od danego końca.
Mój kod ma złożoność O(N*log(N)+N*log(N)) (to drugie to tak naprawdę N*log(len) gdzie len jest max wysokością... ale w najgorszym przypadku to będzie N), a algorytm w książce to O(N*log(N)+N) czyli lepszy... ale tak naprawdę ich algo to O(2N*log(2N)+2N), a 2*N*log(N) jest mniejsze niż 2*N*log(2*N)+N :-) czyli moja priority queue nie była głupim pomysłem ;-) a do tego mój kod jest dużo krótszy ;-)
A i trzecie olśnienie ;-)
Arrays.sort() w Java'ie może używać Comparator.comparing (które robi comparator) i jak sortujemy int[][] to jest wołana wersja Arrays.sort() która operuje na Object[] i jak zrobimy:
Arrays.sort(events, Comparator.comparing(x -> x[0]))
czyli sortujemy wg pierwszego elementu w tablicy (czyli u nas początku) to wszystko śmiga, ale jak dodamy thenComparing:
Arrays.sort(events, Comparator.comparing(x -> x[0]).thenComparing(x -> x[1])
w celu sortowania w razie równości 1 elementu wg drugiego to się nie skompiluje bo biedactwo nie wie jaki jest typ... ale danie mu tego typu problem rozwiązuje ;-)
Arrays.sort(events, Comparator.comparing((int[] x) -> x[0]).thenComparing(x -> x[1])
Zawsze mnie to gryzie jak pisze i stąd wczoraj się temu głębiej przyjrzałem i na razie wiem jak zrobić by działało ;p
Podobne postybetaKiedy skończyć pracę...Java 8 + lambdy = wolno ;-)Wpisy z Bloggera jako eventy w Google Calendar, odsłona 3 - Aplikacja ;-)Wpisy z Bloggera jako eventy w Google Calendar 4 - nowa wersja aplikacji ;-)Java 8 nadchodzi....