Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Jasio uwielbia oglądać telewizję, a szczególnie jego N ulubionych programów. Niestety, z racji tego, że nadawane są na różnych kanałach, czasami nachodzą na siebie w czasie. Jasio musi w takich sytuacjach podjąć trudną decyzję i zdecydować, który program obejrzy. Chłopak woli krótkie programy i stosuje zasadę, zgodnie z którą na pewno nie będzie oglądał programu P, takiego że istnieje inny program Q, który zaczyna się i kończy podczas trwania P. Innymi słowy, jeżeli istnieje para programów P, Q, taka że zachodzi $\text{\textit{początek}}(P) \leq \text{\textit{początek}}(Q)$ oraz $\text{\textit{koniec}}(P) \geq \text{\textit{koniec}}(Q)$, to Jasio nie obejrzy na pewno programu P.
Twoim zadaniem jest obliczenie liczby programów, które Jasio być może obejrzy.
Wejście
W pierwszym wierszu wejścia znajduje się liczba N, oznaczająca liczbę programów. i-ty z następnych N wierszy zawiera dwie liczby Ai, Bi, oznaczające czas początku i końca i-tego programu.
Przedziały czasowe wyznaczane przez programy są parami różne. To znaczy, że nie ma dwóch programów P, Q, dla których jednocześnie $\text{\textit{początek}}(P) = \text{\textit{początek}}(Q)$ oraz $\text{\textit{koniec}}(P) = \text{\textit{koniec}}(Q)$.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się jedna liczba całkowita, oznaczająca liczbę programów, które Jasio być może obejrzy.
Ograniczenia
1 ≤ N ≤ 1 000 000, |Ai|, |Bi| ≤ 109.
Przykład
Wejście | Wyjście | Wyjaśnienie |
|
|
Jasio nie obejrzy programów (2,6), (3,7), (4,8) ze względu na program (4,6), który się w nich czasowo zawiera. |