układanie klocków - zadanie ze skiplistą

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.

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.

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.

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