[m.....s]

Dana jest tablica przedziałów:

array = [

[60, 95],

[15, 40],

[55, 62],

[92, 100],

[17, 30],

[2, 20]

]

Zawartość tej tablicy można zobrazować tak, jak na załączonym obrazku.

Zadaniem jest znalezieniem takie przedziału (bądź punktu) w którym ilość zadeklarowanych w tablicy przedziałów jest największa.

Dla podanego przykładu będzie to przedział [17, 20], ilość 3.

Chodzi mi o znalezienie jak najoptymalniejszego rozwiązania.

Narazie przychodzi mi do głowy jedynie najprostsze rozwiązanie: krokowe sprawdzanie w całym zakresie ilości przedziałów i porównywanie z maxem. Ale takie rozwiązanie jest mało wydajne (delikatnie mówiąc).

Nie potrzebuję implementacji w jakimś konkretnym języku, tylko sposób postępowania. Ktoś ma jakiś pomysł w ten niedzielny poranek?:)

#algorytmy #programowanie #zagadkiprogramistyczne

[Booyaches]

Głowy sobie nie dam uciąć ale to jest chyba tzw. problem Knapsacka i rozwiązuje się go algorytmem Dynamic Programming na przykład.

[hbpitero]

@mk4s: Trudno nazwać jakiekolwiek liniowe rozwiązanie mało wydajnym w czasach, gdy masz do dyspozycji dziesiątki miliardów operacji na sekundę

[hbpitero]

@mk4s: Ale ogólnie to sprawdzał bym tylko końcówki przedziałów, tam gdzie nie ma końców po prostu "nic się nie zmieni".

Całość zależy też od stosunku wielkości całego przedziąłu liczb do ilości przedziałów, liniowość można przyjąć jak to nie będzie jakaś ekstremalnei duża liczba przedziałów

[P.....o]

@mk4s: http://algnotes.wordpress.com/2013/06/03/counting-nested-intervals/

I ogólnie przeszukaj google - nested intervals - bo to zbliżony problem.

[calka]

@Booyaches: imho, problem plecakowy to tutaj trochę na siłę jest wciskany. Niby można traktować kolejne przedziały na osi x(?) i tam starać się maksymalizować wynik, no ale trochę to jest na siłę.

[hbpitero]

@Paulo-Coelho: @calka: problem plecakowy to na pewno nie jest, bo plecakowy jest NP-trudny a tu rozwiązanie w najgorszym wypadku w okolicach N^2 jest banalnie wymyśleć.

Myslę, że nested interval a ten prolem mogą być jednak troche daleko od siebie, szczególnie jak się znajdzie jakieś supersprytne rozwiązanie to może być ciężko je rowinąć do "zachodzenia" na siebie zamiast zawierania.

[ZdzisiuWiesiu]

Chodzi mi o znalezienie jak najoptymalniejszego rozwiązania.

@mk4s: Nie ma czegoś takiego jak "jak najoptymalniejsze" rozwiązanie. Jak coś jest optymalne, to nie da się tego poprawić.

Niektórzy są na to uczuleni, więc warto zapamiętać :)

[m.....s]

@ZdzisiuWiesiu: O widzisz, zawsze staram się dbać o poprawność językową, ale o tym nie widziałem. Zapamiętam i będę stosował, dzięki ;)

[R.....v]

@mk4s: Ja zastosowałem sweeping line. Nie wiem czy jest optymalny i poprawny, musisz to sobie rozpisać i posprawdzać.

http://ideone.com/NY72fi

[F.....d]

@mk4s: zamiatanie wydaje się najnaturalniejszym rozwiązaniem(sposób @Rev).

W skrócie jedziesz od lewej do prawej i obsługujesz zdarzenia, którymi są: natrafienie na początek przedziału, natrafienie na koniec przedziału.

Najpierw trzeba więc posortować początki i końce tych przedziałów(@Rev wrzucił do mapy). To znaczy, że cały algorytm będzie działał w O(nlogn).

[l.....m]

@mk4s: Paulo-Coelho podał dobre rozwiązanie. Możesz je też znaleźć dobrze opisane w Wprowadzeniu do algorytmów Cormena jako problem wyboru zajęć