Прохождение по кортежам в списке. python
Всем привет уже такой вопрос задавал но так и не нашел удовлетворяющий ответ. Напишите функцию sum_of_segments, которая принимает список сегментов и возвращает сумму длин всех сегментов. Перекрытие сегментов должно учитываться только один раз. Сегменты — это пары целых чисел в формате кортежа, например: (2, 7) — это интервал от 2 до 7. Длина этого сегмента равна 5.
Список с перекрывающимися сегментами: [(2, 5), (8, 11), (4, 6)]. Сумма длин этих сегментов равна 7. Поскольку (2, 5) и (4, 6) перекрываются, мы можем рассматривать интервал как (2, 6), который имеет длину 4. И главное функция должна работать не перегружая память если числа будут большими. Примеры: sum_of_segments([(1, 2), (6, 10), (11, 15)]) result is 9
sum_of_segments([(1, 4), (7, 10), (3, 5)]) result is 7
sum_of_segments([(1, 5), (10, 20), (1, 6), (16, 19), (5, 11)]) result is 19
sum_of_segments([(0, 25), (-999999999, 15), (52, 62)]) result is 100000034
fff = [(1, 17), (2, 15), (4, 14), (3, 16)]
def sum_my(segments):
new_list = segments
new_list_tuples = []
for i in range(len(new_list) - 1):
# если в списке у соседних кортежах 2е числа не равны при i+1
if new_list[i][1] + 1 != new_list[i + 1][1]:
# то вычесляем разницу кортежа и добавляем в новый список
new_list_tuples.append(new_list[i][1] - new_list[i][0])
# если равны 2е числа +1
if new_list[i][1] + 1 == new_list[i + 1][1]:
# и у первого кортежа первое число меньше или равно чем у второго кортежа
if new_list[i][0] <= new_list[i + 1][0]:
#
new_list_tuples.append(new_list[i + 1][1] - new_list[i][0])
else:
new_list_tuples.append(new_list[i + 1][1] - new_list[i + 1][0])
print(new_list)
print(new_list_tuples)
print(sum(new_list_tuples))
sum_my(fff)
Проблема я не могу понять как проверить на слияние если таких много в списке
Ответы (1 шт):
Из каждого сегмента сделайте две пары (начало; +1) и (конец; -1). Сложите все пары в один список и отсортируйте его по первому полю.
Теперь задайте active=0 и пройдите по списку. Для каждой пары добавляйте второе поле к active
Если active было 0, а стало 1, запомните позицию (start = первое поле)
Если active стало 0, вычислите разность первого поля со start и добавьте к сумме длин.
В остальных случаях ничего не делать.
Всё.