układanie klocków - zadanie ze skiplistą

Odpowiedz Nowy wątek
2019-05-03 15:05
0

Dany jest ciąg klocków (k_1, ..., k_n). Klocek k_i zaczyna się na pozycji a_i i ciągnie się do pozycji b_i (wszystkie pozycje to liczby naturalne) oraz ma wysokość 1. Klocki układane są po kolei. Jeśli klocek nachodzi na któryś z poprzednich, to jest przymocowywany na szczycie poprzedzającego klocka. Na przykład dla klocków o pozycjach (1,3), (2,5), (0,3), (8,9), (4,6) powstaje konstrukcja o wysokości trzech klocków (vide rysunek). Proszę podać możliwie jak najszybszy algorytm, który oblicza wysokość powstałej konstrukcji (bez implementacji) oraz oszacować jego złożoność obliczeniową.

title

Zadanko jest w temacie skiplisty.
Proszę o pomoc w rozwiązaniu.

edytowany 1x, ostatnio: newbier123, 2019-05-03 15:11

Pozostało 580 znaków

2019-05-03 21:05
0

Pomoc w rozwiązaniu czy rozwiązanie? Za darmo nikt za Ciebie tego nie napisze (chyba że nie za darmo, wtedy zapraszam do działu "Ogłoszenia Drobne").

Pokaż co już sam zrobiłeś i jaki masz pomysł. Ewentualnie na jakim problemie utknąłeś, wtedy ktoś Ci pomoże.


char mander; bool basaur;
Zaawansowana biblioteka T-Regx do wyrażeń regularnych w PHP

Pozostało 580 znaków

2019-05-03 21:10
0

No jedyny pomysl jaki mam to dawac bloczki na skipliste, jaka dlugosc to tyle kolejnych bloczkow odlozyc. Jeśli sie bedzie cos nakladac to dodawac ale z poziomem o jeden większy (poziom węzła w skipliscie).

Jedyne co to mam zaimplementowana skipliste.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0