Ввод: список точек на прямой.
Вывод: Минимальное количество отрезков единичной длинны, с помощью которых можно покрыть все эти точки.
Пример реализации #1. В этом примере мы покрыли все точки 4-мя отрезками, что является не оптимальным решением:
Пример # 2 правильная реализации покрытия:
Так для того, что бы покрыть точки минимальным количество отрезков, необходимо:
- Отсортировать все точки в порядке возрастания.
- Начало первого отрезка равно самой координате первой точки, длинна отрезка по условию = 1
- Находим первую точку координата которой, больше координаты конца отрезка, это будет начало второго отрезка
- …
def sections(coordinates): lines_coordinate = [] points = sorted(coordinates) count_points = len(points) i = 0 while i < count_points: start = points[i] stop = points[i] + 1 lines_coordinate.append([start, stop]) i += 1 while i < count_points and points[i] <= stop: i += 1 return lines_coordinate lst = [0.5, 2, 1, 3.5, 10, 0.7, 1.2] # >>> sorted [0.5, 0.7, 1, 1.2, 2, 3.5, 10] print(sections(lst)) # >>> [[0.5, 1.5], [2, 3], [3.5, 4.5], [10, 11]]