WWywiad Cracking the Coding, wydanie czwarteistnieje taki problem:

Cyrk projektuje rutynową wieżę, składającą się z ludzi stojących na jednym z ramion, z powodów praktycznych i estetycznych, każda osoba musi być zarówno krótsza, jak i lżejsza niż osoba pod nim, zważywszy na wysokość i wagę każdej osoby w cyrku, napisz metodę obliczania największej możliwej liczby osób w takiej wieży.

PRZYKŁAD: Dane wejściowe (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

Wyjście: najdłuższa wieża ma długość 6 i zawiera od góry do dołu: (56, 90) (60,95) (65 100) (68 110) (70 150) (75 190)

Oto jegorozwiązanie w książce

Krok 1 Posortuj wszystkie elementy według wysokości, a następnie według wagi. Oznacza to, że jeśli wszystkie wysokości są unikalne, elementy zostaną posortowane według ich wysokości. Jeśli wysokości są takie same, elementy zostaną posortowane według ich wagi

Krok 2 Znajdź najdłuższą sekwencję, która zawiera rosnące wysokości i rosnące ciężary Aby to zrobić:

a) Rozpocznij na początku sekwencji Obecnie maksymalna_sekwencja jest pusta

b) Jeśli dla następnego przedmiotu wysokość i waga nie są większe niż w poprzednim przedmiocie, oznaczamy ten element jako „niezdatny”

c) Jeśli znaleziona sekwencja ma więcej elementów niż „sekwencja maksymalna”, staje się „sekwencją maksymalną”

d) Następnie wyszukiwanie jest powtarzane z „niezdatnego elementu”, dopóki nie osiągniemy końca oryginalnej sekwencji

Mam kilka pytań dotyczących jego rozwiązań.

Q1

Uważam, że to rozwiązanie jest błędne.

Na przykład

(3,2) (5,9) (6,7) (7,8)

Oczywiście,(6,7) to niezdatny przedmiot, ale co powiesz na to(7,8)? Zgodnie z rozwiązaniem NIE jest on niezdolny, ponieważ jego h i są niepokojące większe niż(6,7)jednak nie można tego rozpatrywać w sekwencji, ponieważ(7,8) nie pasuje(5,9).

Czy mam rację?

Jeśli mam rację, jaka jest poprawka?

Q2

Wierzę, że nawet jeśli istnieje rozwiązanie dla powyższego rozwiązania, styl rozwiązania doprowadzi przynajmniejO(n^2), ponieważ musi powtarzać się wielokrotnie, zgodnie z krokiem 2-d.

Czy więc możliwe jest posiadanie rozwiązania O (nlogn)?