Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.12.2023, 16:46   #1
Nicodim
Пользователь
 
Регистрация: 31.05.2023
Сообщений: 12
По умолчанию Программирование на Python Задача на программирование покрытие отрезками

Помогите пожалуйста разобраться с задачей

По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.

В первой строке дано число 1≤n ≤100 отрезков. Каждая из последующих n строк содержит по два числа
0≤l≤r≤10 в 9 степени, задающих начало и конец отрезка. Выведите оптимальное число m точек и сами
m точек. Если таких множеств точек несколько, выведите любое из них.

Код:
import string
import sys


S = []
n = int(input.readline())
for i in range(1,n+1):
  x,y = map(int, input.readline().split())
  S.append([x,y])



def getKey(item):
    return item[1]
S.sort(key = getKey)
Nicodim вне форума Ответить с цитированием
Старый 28.12.2023, 18:04   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,318
По умолчанию

Код:
S = []
n = int(input())
for _ in range(n):
  l, r = map(int, input().split())
  S.append((l, r))
S.sort()

M = []
l_i, r_i = S[0] # intersection
for l, r in S[1:]:
    l_i_new, r_i_new = max(l, l_i), min(r, r_i)
    if l_i_new > r_i_new:
        M.append(l_i)
        l_i, r_i = l, r
    else:
        l_i, r_i = l_i_new, r_i_new
M.append(l_i)

print(len(M))
print(M)
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 29.12.2023, 21:19   #3
Nicodim
Пользователь
 
Регистрация: 31.05.2023
Сообщений: 12
По умолчанию

Благодарю за помощь!
Nicodim вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программирование на Python Цикл for in Nicodim Помощь студентам 2 04.06.2023 19:57
Программирование в Python fyz abkbvjyjdf Помощь студентам 1 17.12.2022 11:34
Программирование на Python fyz abkbvjyjdf Помощь студентам 11 14.12.2022 19:42
Программирование на python Семен_13 Python 7 17.10.2022 17:59
Программирование Python Белка и Стрелка Помощь студентам 1 29.05.2017 23:53