Maksymalne przecięcie przedziałów

0

Mam oto taki problem:

Dany jest zbiór przedziałów P = {P_1, P_2, .. , P_n} gdzie każdy przedział ma postać P_i = [a_i, b_i], oraz dana jest dodatnia liczba całkowita k. Jak będzie wyglądał algorytm który znajdzie maksymalny przedział który jest przecięciem dokładnie k przedziałów ze zbioru P?

0

Iterujesz po kolei po przedziałach. Dla i-tego iterowanego przedziału próbujesz wybrać ten przedział i zachłannie k-1 sąsiednich (obejmujących go). Złożoność O(n^2 logk).

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