DjangoBB LoFi version

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

Начало » Python для новичков » Кол-во пересечений отрезков

martin

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

Всем привет!

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

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

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

ZerG

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

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

martin

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

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

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

4kpt_IV

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

Interval или interval

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))