Есть несколько диапазонов, заданных начальной и конечной точками: [ (d1_start,

Question

Есть несколько диапазонов, заданных начальной и конечной точками: [ (d1_start,

d1_end), (d2_start, d2_end)]. Отрезки могут пересекаться и/или соприкасаться. Необходимо объединить пересекающиеся отрезки.
Я не долго думая придумал решение O(n^3) (перебираем все пары, если они пересекаются, то убираем оба элемента, вставлям объединение и начинаем всё сначала), но это как-то тупо выглядит. Может есть более умный алгоритм?

#backend #programming #python #russian

0

18.09.2018

3 ответов

8 просмотров

Tishka17

orig.sort() res=[] cur = None for n in orig: if cur is None: cur = n continue if n[0]<=cur[1]: cur = (cur[0], max(cur[1], n[1])) continue res.append(cur) cur=n res.append(cur)

0

18.09.2018

𝕰𝖚𝖌𝖊𝖓 D

Библиотеки можно использовать?

0

18.09.2018

Tishka17 · Accepted Answer

Tishka17

Sort по началу и вперёд в один проход

0

18.09.2018

170 похожих чатов

Есть несколько диапазонов, заданных начальной и конечной точками: [ (d1_start,

3 ответов

Похожие вопросы