Задача к ЕГЭ по информатике на тему «прочие прототипы» №7

Просмотров 7 Комментарии 0

Вам известны координаты начал и концов $n$ отрезков, расположенных на числовой прямой. Сколько существует непересекающихся промежутков, покрытых ровно одним отрезком из данных Вам?

Входные данные:

В первой строке входных данных содержится единственное число $n$ $5 (1 ≤ n ≤ 10 )$ .

Далее в $n$ строках записано по два числа $a$ и $b$ , описывающие отрезки: начало и конец отрезка $(1 ≤ a ≤ b ≤ 109)$ .

Выведите единственное число — количество непересекающихся промежутков, покрытых ровно одним отрезком.

Пример входных данных:

$3$

$1$ $9$

$3$ $4$

$7$ $8$

Пояснение к примеру:

Промежутки $[1,3)$ , $(4,7)$ и $(8,9]$ покрыты ровно одним отрезком. Ответ на данный пример — $3$ .

f = open("file.txt")
n = int(f.readline())
segments = []
for i in range(n):
    a, b = map(int, f.readline().split())
    segments.append((a, 0))
    segments.append((b, 1))

segments.sort()
ans = 0
cur = 0
for i in range(2 * n):
    a, b = segments[i]
    if (b == 0):
        cur += 1
    else:
        cur -= 1
    if (cur == 1):
        ans += 1
print(ans)

Ответ: 3