Implementacja przedziałów na mapie.

Hej,

Ostatnio robiłem zadanie rekrutacyjne, w sumie wydaje mi się że mam dobre rozwiązanie, ale chciałym się z kimś skonsultować :)

Celem jest implementacja klasy opartej na mapie z c++. Chodzi konkretnie o jedna metode. Mapa będzie przechowywać przedziały. Np. jeśli mamy dla klucza o wartości 0, wartość 'CAT', potem dla klucza o wartośći '5', wartosc 'DOG', i dla '10' mamy 'FISH', to należy to rozumieć jako przedziały (0-4) o wartosci CAT, potem (5-9) DOG, i (10 - inf) FISH.

Ogolnie przedzial zaczyna sie od okreslonego punktu, do albo konca mapy, albo do kolejnego roznego punktu.
Zakres kluczy załóżmy że to char, czyli możliwe klucze są od -128 do 127.

Celem zadania jest napisanie funkcji insert(key start, key end, value), która wstawi w przedziale start - end wartosci value. Czyli po prostu stworzy przedział.
Możemy tylko pisać kod w tej funkcji. Czyli may jakaś mape z c++, i możemy sobie z niej korzystać za pomocą standardowych funkcji z C++, ew tego co sami w niej napiszemy.

Pytanie brzmi, jaką najszybciej da się osiągnąć złożoność. W zadaniu była informacja że powinniśmy użyć tylko dwóch operacji o zamortyzowanym koszcie O(logn).

Zupełnie nie rozumiem tego co tu chciałeś opisać. Czyli mam na przykład
0, cat
5, dog
10, fish
i chce dodać (1,2, koza)? I co ma być efektem? W map<char, string> ma mi się znaleźć teraz:
0, cat
1, koza
2, cat
5, dog
10, fish
?
No to gdzie ty tu w ogóle widzisz jakiś problem? Przecież to sie zawsze będzie wiazało tylko z dodaniem nowego elementu do mapy i dodaniem/usunieciem innego. W efekcie masz tutaj albo insert + insert albo insert + find i zarówno jedno jak i drugie jest O(logn) dla mapy implementowanej na drzewie.

Tak twój przypadek z koza jest poprawny i mozesz to zrobic dwoma insertami. Ale co jednak jak poprosze o przedział (-1, 15) 'kura' ? Wtedy musisz zrobić wiecej inserta, i erasy. W pesymistycznym przypadku dla całej przestrzeni kluczy. I w pesymistycznym przypadku masz tutaj liniowe rozwiązanie. A w treści było żeby zrobić to dwoma operacjami o zamortyzowanym koszcie O(logn).
Wydaje mi się że szybciej nie da rady, ale nie jestem pewien czy nie istnieje jakis trick i nie trzeba tyle elementow usuwac.

Masz racje, jeśli nie ma żadnych ograniczeń to może być potrzeba kasowania prawie wszystkich kluczy więc siłą rzeczy musi być to O(n)