это решение работает до тех пор, пока интервалы упорядочены по начальной точке и не требуют создания списка размером с общий диапазон.

код

with open("0.txt") as f:
    t=[x.rstrip("\n").split("\t") for x in f.readlines()]
    intervals=[(int(x[0]),int(x[1])) for x in t]

def find_ints(intervals, mn, mx):
    next_start = mn
    for x in intervals:
        if next_start < x[0]:
            yield next_start,x[0]
            next_start = x[1]
        elif next_start < x[1]:
            next_start = x[1]
    if next_start < mx:
        yield next_start, mx

print list(find_ints(intervals, 0, 200))

выход:

(в случае примера, который вы привели)

[(0, 1), (8, 9), (12, 20), (30, 200)]

Примерный алгоритм:

1. создать массив логических значений, для всех которых установлено значение false seen = [False]*200
2. Переберите входной файл, для каждой строки start end установите seen[start] .. seen[end] равным True
3. После этого вы можете тривиально пройтись по массиву, чтобы найти неиспользуемые интервалы.

С точки зрения оптимизации, если список входных диапазонов отсортирован по начальному номеру, вы можете отслеживать наибольшее увиденное число и использовать его для фильтрации диапазонов по мере их обработки, например. что-то вроде

for (start,end) in input:
  if end<=lowest_unseen:
    next
  if start<lowest_unseen:
    start=lowest_unseen
  ...

который (игнорируя стоимость исходной сортировки) должен сделать все это O (n) - вы проходите через массив один раз, чтобы пометить видимые/невидимые, и один раз, чтобы вывести невидимые.

Кажется, я чувствую себя хорошо. Вот (неоптимизированный) код, предполагая, что ваш входной файл называется input

seen = [False]*200
file = open('input','r')
rows = file.readlines()
for row in rows:
  (start,end) = row.split(' ')
  print "%s %s" % (start,end)
  for x in range( int(start)-1, int(end)-1 ):
    seen[x] = True

print seen[0:10]

in_unseen_block=False
start=1
for x in range(1,200):
  val=seen[x-1]
  if val and not in_unseen_block:
    continue
  if not val and in_unseen_block:
    continue
  # Must be at a change point.
  if val:
    # we have reached the end of the block
    print "%s %s" % (start,x)
    in_unseen_block = False
  else:
    # start of new block
    start = x
    in_unseen_block = True
# Handle end block
if in_unseen_block:
  print "%s %s" % (start, 200)

Я оставляю оптимизацию в качестве упражнения для читателя.

Если вы будете делать пометки каждый раз, когда один из ваших входных интервалов либо открывается, либо закрывается, вы можете делать то, что хотите, складывая вместе ключи opens и closes, сортируя их в упорядоченный набор, и вы сможете по существу думать, «Хорошо, допустим, что каждая соседняя пара чисел образует интервал. Тогда я могу сосредоточить всю свою логику на этих интервалах как на дискретных фрагментах».

myRange = range(201)
intervals = [(1,5), (2,8), (9,12), (20,30)]
opens = {}
closes = {}

def open(index):
    if index not in opens:
        opens[index] = 0
    opens[index] += 1

def close(index):
    if index not in closes:
        closes[index] = 0
    closes[index] += 1

for start, end in intervals:
    if end > start: # Making sure to exclude empty intervals, which can be problematic later
        open(start)
        close(end)

# Sort all the interval-endpoints that we really need to look at
oset = {0:None, 200:None}
for k in opens.keys():
    oset[k] = None
for k in closes.keys():
    oset[k] = None
relevant_indices = sorted(oset.keys())

# Find the clear ranges
state = 0
results = []
for i in range(len(relevant_indices) - 1):
    start = relevant_indices[i]
    end = relevant_indices[i+1]

    start_state = state
    if start in opens:
        start_state += opens[start]
    if start in closes:
        start_state -= closes[start]

    end_state = start_state
    if end in opens:
        end_state += opens[end]
    if end in closes:
        end_state -= closes[end]
    state = end_state

    if start_state == 0:
        result_start = start
        result_end = end
        results.append((result_start, result_end))

for start, end in results:
    print(str(start) + " " + str(end))

Это выводит:

0 1
8 9
12 20
30 200

Интервалы не нужно сортировать.

Этот вопрос кажется дубликатом Объединение интервалов в Python.

Если я правильно понял задачу, у вас есть список интервалов (1 5; 2 8; 9 12; 20 30) и диапазон (0 200), и вы хотите получить позиции за пределами ваших интервалов, но внутри заданного диапазона. Верно?

В этом вам может помочь библиотека Python: python-intervals (также доступно в PyPI с использованием pip). Отказ от ответственности: я являюсь сопровождающим этой библиотеки.

Предположим, вы импортируете эту библиотеку следующим образом:

import intervals as I

Получить ответ довольно легко. По сути, вы сначала хотите создать дизъюнкт интервалов на основе тех, которые вы предоставляете:

inters = I.closed(1, 5) | I.closed(2, 8) | I.closed(9, 12) | I.closed(20, 30)

Затем вы вычисляете дополнение этих интервалов, чтобы получить все, что находится «снаружи»:

compl = ~inters

Затем вы создаете объединение с [0, 200], так как хотите ограничить точки этим интервалом:

print(compl & I.closed(0, 200))

Это приводит к:

[0,1) | (8,9) | (12,20) | (30,200]