[NotABigFan]

Dziś zadanie od Snapchat.

Mając podaną tablicę przedziałów czasowych (początek, koniec), w których odbywają się wykłady, określ minimalną liczbę sal potrzebnych do przeprowadzenia wszystkich wykładów.

np. dla [(30, 75), (0, 50), (60, 150)] właściwa odpowiedź to 2.

#dailycodingproblem #programowanie

[ptasigryp]

@NotABigFan: Mam taki pomysł:
-Załóżmy, że rezerwować czas można z dokładnością co do 5 minut, jeśli jest potrzeba co do minuty to można zmodyfikować algorytm ale zajmie więcej czasu i pamięci.
-Robimy tablice timeline'u (np. index 0 to 0 min, index 1 to 5 minuta, index 2 to 10 minuta itd) w którą wstawiamy moment rozpoczęcia i zakończenia wykładu.
-Następnie lecimy od początku do końca tej tablicy i trzymamy zmienną

[ptasigryp]

@NotABigFan: Można to w sumie uprościć i nawet nie trzymać całego timeline'u, a same kluczowe momenty (rozpoczęcie, zakończenie).

[T.....n]

@NotABigFan: metoda dowolna?
rozwiązanie musi być optymalne?
ilość przedziałów czasowych maksymalna jest określona?
podane sa one w minutach (timestamp)?

[T.....n]

Można to w sumie uprościć i nawet nie trzymać całego timeline'u, a same kluczowe momenty (rozpoczęcie, zakończenie).

@ptasigryp: istotne sa tylko gapy
nakładające się okresy
maksymlana ilość gapów w tym samym momencie oznacza ilość sal

[nesti32]

@NotABigFan: Edit jednak zle mowie xD

[ptasigryp]

@nesti32: Ilość wspólnych zbiorów + 1 wydaje mi się, że zawsze zadziała, tylko czy jest coś sprawniejszego niż n^2?

[daczka92]

@ptasigryp: tez tak pomyslalem. Zapisujemy wtedy jaka maksymalna wartość wystapila przy tym dodawaniu i odejmowaniu

[nesti32]

@ptasigryp: @daczka92: Na pewno jest, ale cos mi w glowie sie nie uklada, poniewaz z sortowaniem po czasie na pewno daloby sie pozniej przejsc liniowo i sprawdzac przeciacia, -> nlogn

[NotABigFan]

@ptasigryp: Może uściślij nieco, jeśli to dobrze rozumiem to będzie miało złożoność O(maksymalny czas)
@TwojStaryToKorniszon:

metoda dowolna?

Tak, ale w ramach tego co

[NotABigFan]

podane sa one w minutach (timestamp)?

@TwojStaryToKorniszon: czyli możesz założyć że tak

[ptasigryp]

@NotABigFan: @TwojStaryToKorniszon: @nesti32: Zrobiłem, chyba działa :)
https://pastebin.com/9tKfwmnH

[NotABigFan]

@ptasigryp: Czyli O(maksymalny czas), w sumie w praktyce by uszło ( ͡° ͜ʖ ͡°)

[ptasigryp]

@NotABigFan: Nie przychodzi mi do głowy nic wydajniejszego. Prócz tego mój algorytm nie pokrywa obecnie sytuacji np. rezerwacji sali o 22 do 2 w nocy.

[NotABigFan]

@ptasigryp: @nesti32: ma dobry trop

[ptasigryp]

@NotABigFan: Posortować algorytmem z n*logn, następnie robić przejście z lewej do prawej na dwóch indexach (miało to jakąś profesjonalną nazwę).
Index j wyprzedza index i, zlicza następne rezerwacje które mają otwarcie <= zamknięciu rezerwacji na indexie i, gdy natrafi na coś późniejszego to i++, j leci dalej sprawdzając czy coś następnego otwiera się przed zamknięciem.

Nie mam teraz głowy do zakodowania tego i nie wiem czy ten pomysł nie padnie

[NotABigFan]

miało to jakąś profesjonalną nazwę

@ptasigryp: zamiatanie ( ͡° ͜ʖ ͡°)

[NotABigFan]

@koperrr: źródło podało, że to od snapchata. Prawda to czy nie znaczna większość tych zadań mogłaby być zadawana w każdej z tych firm.

[S.....s]

@ptasigryp: chyba nawet prościej bez tych 5 minut tylko posortować zdarzenia i sumować
https://pastebin.com/GLgb68p0

[ptasigryp]

@SuppressWarnings: czy przypadkiem 'if a[0] not in events' nie ma złożoność O(n)? To by sprawiało, że w pętli o złożoności O(n) wywołujesz kolejne O(n) czyli O(n^2).