算法:使用关联键重叠 1D 段

Question

给定逻辑时间的输入和每个时间的唯一键，我如何返回逻辑时间的总序列(可能被分解)以识别那个时间“存在”的每个键？

例如，逻辑时间作为简单整数(可以递增或递减)，以及可以比较的键:

type LogicalTime = Int
type Key = Char

-- Not necessarily ordered
skipList :: [(LogicalTime, LogicalTime, Key)]
skipList = 
    [ (100, 200, 'A')
    , (201, 300, 'B')
    , ( 20, 400, 'C')
    , (125, 150, 'D')
    , (151, 250, 'E')
    ]

expected :: [(LogicalTime, LogicalTime, [Key])]
expected =
    [ ( 20,  99, ['C'])
    , (100, 124, ['A','C'])
    , (125, 150, ['A','C','D'])
    , (151, 200, ['A','C','E'])
    , (201, 250, ['B','C','E'])
    , (251, 300, ['B','C'])
    , (301, 400, ['C'])
    ]

尽管我正在寻找一种更有效的方法，但人们可能天真地遍历找到的整个范围并循环遍历每个键条目来计算它。(这不是特定于语言的)

Answer 1

每个间隔 (start, end, key) 触发两个事件:add(key,start) 和 remove(key,end) .在遍历间隔列表时生成这些事件，然后按事件的时间(start 或 end)对事件进行排序。然后，您可以遍历已排序的事件，生成一个在具有事件键的事件之前结束的间隔，并更新下一个间隔的键数。

这是一些 python 代码:

events = []
for start,end,key in skipList:
  events.extend([(start-1, 1, key), (end, -1, key)])
events.sort()

startTime,_,firstKey = events.pop(0)
activeKeys = {firstKey:1}
expected = []
for time,delta,key in events:
  currentKeys = [k for k in activeKeys if activeKeys[k] > 0]
  currentKeys.sort()
  if startTime < time:
    expected.append((startTime+1, time, currentKeys))
  if not key in activeKeys:
    activeKeys[key] = 0
  activeKeys[key] += delta
  startTime = time

对于您的示例，skipList 生成了预期 的输出。