Question

Dostępna pamięć: 32 MB.
Jestes kinomanem, chcesz obejrzec jednego dnia jak najwiecej seansów filmowych. W kinie odbedzie sie n seansów. i-ty seans zaczyna sie w czasie si i konczy sie w czasie ´ ki (si < ki). Jesli decydujesz sie na ogladanie jakiegos seansu, to ogladasz go w ´ całosci(od poczatku do konca), po czym mozesz przejsc sie na kolejny seans. Zakładamy, ´ ze po obejrzeniu seansu ˙ i jestes w´ stanie wybrac jako nastepny seans j jesli ´ ki < sj . Twoim zadaniem jest powiedziec, ile maksymalnie seansów mozesz obejrzec.
Wejscie ´
W pierwszym wierszu znajduje sie liczba całkowita n (1 ≤ n ≤ 100,000), ilosc seansów filmowych. W nastepnych ´ n wierszach znajduja sie po dwie liczby całkowite si , ki (0 ≤ si < ki ≤ 109 ). Sa to czasy rozpocz˛ecia i zakonczenia kolejnych seansów ´ filmowych.
Wyjscie ´
Na wyjsciu nalezy wypisac jedna liczbe całkowita - maksymalna ilosc seansów, które mozesz obejrzec.
Przykład
Dla danych wejsciowych: ´ 5 3 5 6 10 2 4 1 4 10 14 poprawnym wynikiem jest: 2

C++

Answer 1

Okej, więc algorytm wygląda tak, że bierzemy zawsze seans który kończy się najwcześniej.
Dowód (mało formalny):
Weźmy odcinek o najmniejszym końcu (s1, k1) oraz dowolny odcinek (s2, k2) spełniający warunek s2<=k1. Oba odcinki należą do zbioru R (odcinki z zadania) oraz załóżmy, że jeden z tych odcinków należy do zbioru rozwiązań. (Widać, że jeśli odcinek (s1, k1) nie należy do zbioru rozwiązań, to należy jakis odcinek (si, ki) gdzie si<=k1, ponieważ gdyby nie należał, to odcinek (s1, k1) nie kolidowałby z zadnym innnym i moglibysmy go wybrac)

Niech zbiór R zawiera wszystkie odcinki z zadania.

Niech R1=R2=R.
z R1 wyrzucamy wszystkie kolidujące odcinki z (s1, k1) (oraz sam odcinek), a ze zbioru R2 wszystkie kolidujące z (s2, k2) (tak samo).
R1 = R - {(si, ki)| si <=k1 }
R2 = R - {(si, ki)| ki nalezy <s2, k2> lub si nalezy <s2, k2> }
R2 = R - {(si, ki)| ki nalezy <s2, k2>} - {(si, ki)| si nalezy <s2, k2> }
R2 = R - {(si, ki)| ki nalezy <s2, k2>} - {(si, ki)| si <=k2 i si >= s2 }

{(si, ki)| si <=k1 } jest podzbiorem {(si, ki)| si <=k2 i si >= s2 }, ponieważ k1<=k2 . A z tego wynika, że R2 jest podzbiorem R1. Więc udowodniliśmy w ten sposób, że odcinek (s1, k1) należy do zbioru rozwiązań.

Dalej postępujemy indukcyjnie, aż R1={} i R2={}

Wyjaśnienie na "chłopski rozum". W R1 jest więcej kandydatów na bycie dobrym odcinkiem, przy czym w R2, nie znajdują się odcinki, które nie znajdują się w R1. Więc widzimy, że bardziej opłaca się wybrać odcinek (s1,k1), a udowodniliśmy, że któryś z tych dwóch, należy do zbioru rozwiązań.

Mam nadzieję, że pomogłem :) Nie jestem dobry w formalnych dowodach, ale myślę, że zrozumiałeś o co chodzi. Przykładowy kod w załączniku.