3

我的问题如下：

有间隔列表的文件：

1 5
2 8
9 12
20 30

以及一系列

0 200

我想做这样一个交叉点，它将报告给定范围内我的间隔之间的位置 [start end]。

例如：

8 9
12 20
30 200

除了如何解决这个问题的任何想法之外，阅读一些关于优化的想法也很不错，因为输入文件将一如既往地巨大。

4

4 回答 4

3

只要间隔按起点排序并且不需要创建与总范围一样大的列表，此解决方案就可以工作。

代码

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)]
于 2013-08-23T10:57:39.030 回答
1

粗略算法：

  1. 创建一个布尔数组，全部设置为 falseseen = [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)

我将优化留给读者作为练习。

于 2013-08-23T09:56:13.983 回答
1

如果您在每次输入间隔打开或关闭时都记下，您可以通过将opensand的键放在一起来做您想做的事情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

间隔不需要排序。

于 2013-08-23T10:42:54.923 回答
1

这个问题似乎与Python 中的 Merging interval重复。

如果我很好地理解了这个问题，那么您有一个区间列表（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]
于 2018-04-08T14:10:55.527 回答