Тестируется через stdin → stdoutПо данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.
В первой строке дано число 1≤n≤100
отрезков. Каждая из последующих n строк содержит по два числа 0≤l≤r≤109, задающих начало и конец отрезка. Выведите оптимальное число m точек и сами m точек. Если таких множеств точек несколько, выведите любое из них.
Сразу оговорюсь, прошу не комментировать само мое решение, мне важно чтобы алгоритмическую часть я решал самостоятельно, это все же обучение.
Мой код:
Код: Выделить всё
import sys
lineIn = sys.stdin.readline()
n = int(lineIn)
r_l = []
for i in range(n):
lineIn = sys.stdin.readline().split(" ")
l_tmp = (int(lineIn[0]))
r_tmp = (int(lineIn[1]))
r_l.append([r_tmp, l_tmp])
r_l.sort()
m_coord = []
m_coord.append(r_l[0][0])
m = 1
for i in range(n):
if r_l[i][1] > m_coord[(len(m_coord) - 1)]:
m = m + 1
m_coord.append(r_l[i][0])
sys.stdout.write(str([m, m_coord]))
Failed test #1. wrong output format: invalid literal for int() with base 10: '[1,'
Input:
3
1 3
2 5
3 6
Your output:
[1, [3]]
Correct output:
1
3