Python-сообщество

martin · Янв. 27, 2017 11:34:12

Всем привет!

Допустим есть список числовых отрезков (от ЧИСЛО, до ЧИСЛО)

 data = [
   (100, 200),
   (50, 250),
   (240, 500),
   (700, 800),
   (900, 1000),
]

Как найти, сколько отрезков пересекаются в данном списке? (в представленном примере это = 3, первые три отрезка пересекаются), если кол-во отрезков может быть несколько тысяч? Существуют ли какие быстрые алгоритмы и т.п.?

Отредактировано martin (Янв. 27, 2017 12:08:29)

ZerG · Янв. 27, 2017 11:40:18

не понятно по какой логике они пересекаются?
Я например в упор не вижу пересечений

Влодение рускай арфаграфией - это как владение кунг-фу: настаящие мастира не преминяют ево бес ниабхадимости

martin · Янв. 27, 2017 12:06:42

ZerG
не понятно по какой логике они пересекаются? Я например в упор не вижу пересечений

я имел ввиду числовые отрезки от и до, например (100, 200) = от 100 до 200

Отредактировано martin (Янв. 27, 2017 12:07:35)

4kpt_IV · Янв. 27, 2017 13:09:28

Interval или interval

Отредактировано 4kpt_IV (Янв. 27, 2017 13:11:17)

FishHook · Янв. 27, 2017 14:13:31

Да вы сбрендили, ради такой плевой задачки сторонний код подключать?

 data = [
   (100, 200),
   (50, 250),
   (240, 500),
   (700, 800),
   (900, 1000),
]
from itertools import combinations
for (a, b), (a1, b1) in combinations(data, 2):
    if a < a1:
        is_intersect = a <= a1 <= b
    else:
        is_intersect = a1 <= a <= b1
    if is_intersect:
        print("({}, {}) intersects ({}, {})".format(a, b, a1, b1))

Python-сообщество

Уведомления

#1 Янв. 27, 2017 11:34:12

Кол-во пересечений отрезков

#2 Янв. 27, 2017 11:40:18

Кол-во пересечений отрезков

#3 Янв. 27, 2017 12:06:42

Кол-во пересечений отрезков

#4 Янв. 27, 2017 13:09:28

Кол-во пересечений отрезков

#5 Янв. 27, 2017 14:13:31

Кол-во пересечений отрезков

Board footer