• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Znajdź przedział zawierający największą ilość przedziałów

VPS Starter Arubacloud
0 głosów
377 wizyt
pytanie zadane 16 marca 2022 w Algorytmy przez essownik Nowicjusz (120 p.)
Dostałem za zadanie znaleźć przedział liczbowy <a,b> który zawiera największą ilość przedziałów. Wszystkie przedziały podane są na wejściu w postaci listy [[start,koniec],[start2,koniec2],[start3,koniec3]] Jedyne co mi przychodzi do głowy to bruteforce o złożoności n^2, wiem że żeby wykonać poprawnie zadanie potrzebny jest algorytm o złożoności nlogn. Myślałem żeby zrobić dwie tablice, jedna która zawiera posortowane początki, druga która zawiera posortowane końce. Następne coś pokombinować przeszukiwaniem binarnym ale w tym miejscu utknąłem. Proszę o pomoc

1 odpowiedź

0 głosów
odpowiedź 16 marca 2022 przez adrian17 Ekspert (344,100 p.)

Myślałem żeby zrobić dwie tablice, jedna która zawiera posortowane początki, druga która zawiera posortowane końce

Na intuicję:

Zrób jedną tablicę z posortowanymi wszystkimi punktami oraz informacją którego przedziału jest początkiem/końcem.

Wtedy możesz liniowo iterując się po tej tablicy zliczać ile podprzedziałów należy do każdego przedziału i na koniec wybrać najlepszy.

komentarz 16 marca 2022 przez essownik Nowicjusz (120 p.)
rozumiem że jeżeli mam przedziały np. <2,6> <1,4> <2,5> <5,8> <4,5> to moja jedna tablica będzie taka
<1,2,2,4,4,5,5,5,8>
czyli inaczej si - start i-tego przedziału ki - koniec i-tego przedziału (zakładając numerację np. od 1)
<s2,s1,s3,s5,k2,k3,k5,s4,k1,k4>
I teraz widzę że s1 zawiera w sobie s3,s5,k2,k3,k5,s4 czyli 2 pełne przedziały
Dobrze rozumiem rozwiązanie?
komentarz 16 marca 2022 przez adrian17 Ekspert (344,100 p.)

I teraz widzę że s1 zawiera w sobie s3,s5,k2,k3,k5,s4 czyli 2 pełne przedziały

To jest duży skrót myślowy, bo ten krok to "iterując się po tej tablicy, wypełniaj drugie mapowanie/tablicę/etc z informacją dla każdego przedziału, jakie są w nim naczęte/pełne przedziały".

Ale ogólnie tak, tak bym to zrobił.

komentarz 16 marca 2022 przez essownik Nowicjusz (120 p.)
tak tak tak, właśnie tak myślałem ale nie chciał konkretnie pytać, bo żeby zmapować to przy posortowaniu będzie trzeba w drugiej tablicy zmieniać oznaczenia tak żeby nie zgubić elementów
komentarz 16 marca 2022 przez essownik Nowicjusz (120 p.)

@adrian17, mam jeszcze jedno pytanie jak już będę miał te tablice to przypadkiem przeszukanie nie będzie kwadratowę? Bo jakby dla każdego przedziału będę liczył ile przedziałów znajduję się między jego początkiem i końcem w tablicy tak żeby znaleźć największy

komentarz 16 marca 2022 przez adrian17 Ekspert (344,100 p.)

Bo jakby dla każdego przedziału będę liczył ile przedziałów znajduję się między jego początkiem i końcem w tablicy

Nie tak; napisałem:

Wtedy możesz liniowo iterując się po tej tablicy zliczać ile podprzedziałów należy do każdego przedziału

Jedno przejście po tablicy analizujące wszystkie przedziały na raz. Przynajmniej tak bym na intuicję zrobił, z jakąś hashmapą - pseudokod około-Pythonowy:

contained_starts = dict() # Dict[interval_id, Set[interval_id]]
counts = dict() # Dict[interval_id, int]
current_intervals = set() # Set[interval_id]

for interval_id, start_or_end in sorted_points:
	if start_or_end == "start":
		for outer_interval in current_intervals:
			contained_starts[outer_interval].add(interval_id)
		current_intervals.add(interval_id)
	else: # end
		current_intervals.remove(interval_id)
		# when an interval ends, increment count of every outer interval that also saw its start by 1
		for outer_interval in current_intervals:
			if interval_id in contained_starts[outer_interval]:
				counts[interval_id] += 1

best_interval = counts.max_key_by_value()

I to się wydaje być n log n.

Natomiast nie ukrywam że im dłużej na to patrzę, tym bardziej mam wrażenie że da się prościej ;) Ale z głowy nie mam pomysłu.

komentarz 16 marca 2022 przez essownik Nowicjusz (120 p.)
a własnie, bo nie dodałem. W założeniach zadaniach jakie dostałem jest napisane że z jedynych gotowych struktur danych z których można korzystać to krotka (tuple) bądź tablica, nie wspominałem bo myślałem że nie będzie to potrzebne
komentarz 16 marca 2022 przez adrian17 Ekspert (344,100 p.)
Hmm... też nie wiem :( Miałem kilka innych pomysłów, ale wszystkie wykraczały poza "same tablice", w dodatku nie miałem gwarancji że nie będą kwadratowe (w tym moim wcześniejszym pseudokodzie w sumie tez są przypadki gdzie może być kwadratowe)...

Podobne pytania

0 głosów
2 odpowiedzi 277 wizyt
pytanie zadane 18 października 2022 w C i C++ przez Perkol02 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 294 wizyt
pytanie zadane 21 stycznia 2023 w Algorytmy przez hharry33 Nowicjusz (150 p.)
0 głosów
1 odpowiedź 302 wizyt

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...