Сохранение данных с одним и тем же первичным ключом в обеих иерархиях в hibernate Присоединение к таблице наследования

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

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)

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