Условие задачи
Даны отрезки на прямой. Какое максимальное количество отрезков можно выбрать так, чтобы никакие два из них не пересекались? Отрезки считаются открытыми.
Алгоритм решения
Нам даются отрезки, из которых необходимо набрать максимальное количество так, чтобы никакие два не пересекались.
1. Сортируем отрезки по правому краю: так мы будем знать отрезок, который заканчивается первым, следовательно, он никому дальше не помешает, сортируем отрезки именно по правому краю, так как нам важнее тот факт, чтобы они не пересекались.
2. Далее мы запоминаем номер отрезка, который взяли (сначала в переменной будет храниться 0, так как самый первый отрезок заканчивается раньше всех, значит, мы его точно берем). И заводим переменную, которая хранит количество отрезков (изначально = 1, так как первый отрезок уже взяли).
3. Проходимся по списку кортежей (пример: [(1,4), (3,6), (7,10)]) и сравниваем конец отрезка, который мы взяли с началом нового отрезка. То есть, если следующий по счету отрезок не накладывается на отрезок, который мы уже взяли, то мы берем новый отрезок и запоминаем его номер в переменной.
4. Выводим ответ.
Код программы на Python
import sys
v = []
n = int(input())
for i in range(n):
k, q = map(int, input().split())
v.append((k,q))
v.sort(key = lambda x: (x[1], x[0]))
cur=0
res=1
for i in range(1,n):
if v[i][0] >= v[cur][1]:
cur = i
res+=1
if (n==0):
print(0)
else:
print(res)
Буду рада оставленному лайку и комментарию, если мой разбор вам помог.
Пишите, какие задачи нужно разобрать!
#информатика #программирование #codeforces #репетитор по информатике #python