Если вы делаете заметку каждый раз, когда один из ваших интервалов ввода открывается или закрывается, вы можете делать то, что хотите, объединяя ключи 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-interval (также доступен из 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]

Грубый алгоритм:

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) - вы проходите через массив один раз, чтобы пометить увиденное / невидимое и один раз вывести unseens.

Кажется, я чувствую себя хорошо. Вот код (неоптимизированный), предполагающий, что ваш входной файл называется 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)

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