Scalanie przedziałów

Zadanie 6 z 14 · rozdział 13Trudność: 2 z 3sortowanieprzedziałyalgorytmy

Treść zadania

Wczytaj n przedziałów domkniętych $[a_i, b_i]$. Scal wszystkie przedziały, które na siebie nachodzą, i wypisz otrzymane rozłączne przedziały w kolejności rosnącej według początku.

Dane wejściowe

  • 1. linia: n
  • następnie n linii, w każdej dwie liczby całkowite a_i b_i (a_i ≤ b_i)

Dane wyjściowe

Każdy scalony przedział w osobnej linii w postaci a b, posortowane rosnąco według a.

Ograniczenia

  • 1 ≤ n ≤ 1000
  • $-10^6 \le a_i \le b_i \le 10^6$

Uwagi

  • Przedziały na wejściu mogą być podane w dowolnej kolejności — najpierw je posortuj.
  • Dwa przedziały (po posortowaniu) nachodzą na siebie, gdy początek następnego jest mniejszy lub równy końcowi bieżącego. Przedziały stykające się końcami, np. 1 3 i 3 5, scalamy w 1 5, natomiast 10 22 i 23 88 pozostają osobno.

Przykład

Wejście
7
23 67
23 53
45 88
77 88
10 22
11 12
42 45
Wyjście
10 22
23 88

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 13

Zadania w tym rozdziale ćwiczą pracę z listami dwuwymiarowymi (macierzami): tworzenie, wczytywanie, przechodzenie po wierszach i kolumnach oraz przekształcanie.
Każde zadanie (oraz każdy podpunkt) jest osobnym, niezależnym programem: czyta standardowe wejście (stdin) i wypisuje wynik na standardowe wyjście (stdout).

Konwencje wspólne:

  • Dane wczytuj dokładnie w kolejności podanej w sekcji Wejście.
  • Wiersz macierzy na wejściu to jedna linia z liczbami oddzielonymi spacjami — wczytaj całą linię i rozbij ją po spacjach (input().split()).
  • W wyjściu macierzy: każdy wiersz w osobnej linii, elementy oddzielone pojedynczą spacją.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
4
1 3
2 6
8 10
9 12
Oczekiwane wyjście
1 6
8 12

Test 2

Nie uruchomiono
Wejście
2
5 7
1 2
Oczekiwane wyjście
1 2
5 7

Test 3

Nie uruchomiono
Wejście
2
1 3
3 5
Oczekiwane wyjście
1 5

Test 4

Nie uruchomiono
Wejście
1
4 4
Oczekiwane wyjście
4 4

Test 5

Nie uruchomiono
Wejście
3
1 10
2 3
4 5
Oczekiwane wyjście
1 10

Test 6

Nie uruchomiono
Wejście
4
-5 -1
0 2
-2 0
6 9
Oczekiwane wyjście
-5 2
6 9
Uruchom z własnymi danymi