algorithm - 确定最长的连续子序列

Question

沿着a有N个节点(1 <= N <= 100,000)不同的位置长的一维长度。第 i 个节点位于位置 x_i (an0...1,000,000,000 范围内的整数)并且节点类型为 b_i(整数范围 1..8)。节点不能在同一个位置

您想在这个一维上获得一个范围，其中所有类型的节点都得到了公平的表示。因此，您要确保对于范围内存在的任何类型的节点，每种节点类型的数量都相等(例如，类型 1 和类型 3 各有 27 个的范围是可以的，范围有 27 个类型 1、3 和 4 的是好的，但是类型 1 的 9 和类型 3 的 10 是不行的)。你也想要至少有 K (K >= 2) 种类型(总共 8 种)要在兰特。找到满足约束的此范围的最大大小。照片的大小是照片中节点的最大位置和最小位置之差。

如果没有满足约束的范围，则输出-1。

INPUT:

* Line 1: N and K separated by a space

* Lines 2..N+1: Each line contains a description of a node as two
        integers separated by a space; x(i) and its node type.

INPUT:

9 2  
1 1  
5 1  
6 1  
9 1  
100 1  
2 2  
7 2  
3 3  
8 3     

INPUT DETAILS:  
Node types: 1 2 3 - 1 1 2 3 1  - ...  -   1  
  Locations: 1 2 3 4 5 6 7 8 9 10 ... 99 100

OUTPUT:

* Line 1: A single integer indicating the maximum size of a fair
       range. If no such range exists, output -1.

OUTPUT:

6

OUTPUT DETAILS:

The range from x = 2 to x = 8 has 2 each of types 1, 2, and 3. The range
from x = 9 to x = 100 has 2 of type 1, but this is invalid because K = 2
and so you need at least 2 distinct types of nodes.

你能帮忙推荐一些算法来解决这个问题吗？我考虑过使用某种优先级队列或堆栈数据结构，但我真的不确定如何进行。

谢谢，托德

Answer 1

发明几乎线性时间的算法并不难，因为最近在 CodeChef 上讨论了类似的问题:"ABC-Strings" .

1. 按位置对节点进行排序。
2. 准备节点类型的所有可能子集(例如，我们可以预期类型 1、2、4、5、7 出现在结果区间中，而所有其他类型不出现在那里)。对于 K=2，可能只有 256-8-1=247 个子集。对于每个子集执行剩余的步骤:
3. 将 8 个类型的计数器初始化为 [0,0,0,0,0,0,0,0]。
4. 对每个节点执行剩余步骤:
5. 当前节点类型的增量计数器。
6. 为包含在当前子集中的类型取 L 个计数器，从其他 L-1 计数器中减去第一个，得到 L-1值。取剩余的 8-L 计数器并将它们与那些 L-1 值组合成一个包含 7 个值的元组。
7. 使用这个元组作为 HashMap 的键。如果 HashMap 不包含此键的值，则添加一个新条目，此键和值等于当前节点的位置。否则从当前节点的位置减去 HashMap 中的值并(可能)更新最佳结果。