保持相对排序且同类型元素间隔至少k的算法需求

我有一个包含id、type、rank字段的元素列表，列表已按rank排序。数据随机分布，各类元素占比无固定规律。需求如下：

• 让同类型元素之间至少间隔k个位置；
• 若无法满足上述要求，则尽量使同类型元素的间隔最大化；
• 必须保持同类型元素的相对排序（比如原列表中先出现的同类型元素，在结果里不能晚于原列表中后出现的同类型元素）；
• 列表规模约1000，优先保证算法正确性，不追求最优性。

示例：原列表为[(1,A,1),(2,A,2),(3,B,3),(4,B,4),(5,C,5)]，当k=2时，期望结果为[(1,A,1),(3,B,3),(2,A,2),(4,B,4),(5,C,5)]

类似问题：分离同类型元素的算法

这个方法既能保证同类型元素的相对排序，又能满足间隔要求（或尽量最大化间隔），实现简单且正确性有保障，适合1000规模的列表。

具体步骤 #

1. 分组建队列：按type对元素分组，每个组内的元素严格保留原列表中的顺序（也就是按rank升序），每个组对应一个队列。比如示例中，A类型队列是[(1,A,1), (2,A,2)]，B类型队列是[(3,B,3), (4,B,4)]，C类型队列是[(5,C,5)]。
2. 初始化辅助结构：创建空的结果列表result，再创建一个长度为k的窗口（用来记录结果列表中最后k个元素的类型，初始为空）。
3. 循环构建结果：直到所有队列都为空，重复以下操作：
   • 筛选候选队列：遍历所有非空队列，检查队列头部元素的type是否不在当前窗口中（即结果列表最后k个位置里没有同类型元素）。
   • 选择待插入元素：从候选队列中，挑出头部元素rank最小的那个（保证整体的相对排序符合原列表的rank顺序）；如果没有候选队列（所有非空队列的头部元素类型都在窗口里），就直接挑头部元素rank最小的队列。
   • 更新结果和窗口：把选中的元素从队列中取出，加入result；同时更新窗口——如果窗口已满，移除最早加入的类型，再把当前元素的type加入窗口。

示例验证 #

用题目给出的例子走一遍流程：

• 初始队列：A:[(1,A,1),(2,A,2)], B:[(3,B,3),(4,B,4)], C:[(5,C,5)]，窗口为空。
• 第一次选择：所有队列都符合条件，选rank最小的(1,A,1)，结果列表变为[(1,A,1)]，窗口更新为[A]。
• 第二次选择：A队列头部元素类型在窗口中，不符合；B队列头部(3,B,3)符合，选中加入结果，列表变为[(1,A,1),(3,B,3)]，窗口更新为[A,B]。
• 第三次选择：A队列头部(2,A,2)的类型不在窗口中，符合；C队列也符合，选rank更小的(2,A,2)加入，列表变为[(1,A,1),(3,B,3),(2,A,2)]，窗口更新为[B,A]。
• 第四次选择：B队列头部(4,B,4)的类型不在窗口中，符合；C队列也符合，选rank更小的(4,B,4)加入，列表变为[(1,A,1),(3,B,3),(2,A,2),(4,B,4)]，窗口更新为[A,B]。
• 第五次选择：只剩C队列，直接加入(5,C,5)，最终结果和题目期望完全一致。

• 这个方法严格保证了同类型元素的相对顺序：因为每个队列里的元素是按原列表顺序排列的，每次只取队列头部的元素，不会打乱同类型内部的顺序。
• 当无法满足间隔k的要求时，会优先选择rank最小的元素插入，这样能尽量让同类型元素的间隔最大化——因为我们是在所有可选的“不得不插入”的元素里，选最应该先出现的，避免同类型元素扎堆。

内容的提问来源于stack exchange，提问作者darkbot