求最大停留时长M下可获取最多实体的T_n及高效算法

问题明确 #

先明确核心规则：

1. 实体分为两类：
   • 免费实体：start == end，自动计入总数，归属其所在的T_n
   • 非免费实体：start < end，需被停留窗口覆盖才计入总数；停留窗口是时长≤M的时间区间[L, R]（R-L ≤ M），实体被覆盖的条件是与窗口有交集（实体.start ≤ R 且 实体.end ≥ L）
2. 可选择任意多个不重叠的停留窗口，目标是最大化总实体数（免费实体总数 + 被覆盖的非免费实体数），同时记录对应的T_n（包含所有有免费实体的T_n，以及有非免费实体被覆盖的T_n）

预处理阶段 #

1. 拆分实体：遍历所有T_n，分离出两类实体：
   • 统计免费实体总数total_free，并记录包含免费实体的T_n到集合free_groups
   • 收集非免费实体为列表non_free，每个元素存储为(start, end, group)，其中group标记该实体所属的T_n（如T_0对应0，T_1对应1）
2. 排序非免费实体：将non_free按实体的end从小到大排序，这是贪心策略的核心，确保优先处理结束最早的实体，最大化后续窗口的覆盖范围。

核心算法：贪心+二分批量覆盖 #

该算法时间复杂度为O(N log N)（N为非免费实体总数），远优于滑动窗口法的O(N*T)（T为时间范围）：

1. 提取排序后non_free的所有start值到列表starts，方便后续二分查找
2. 初始化变量：
   • covered = [False] * len(non_free)：标记实体是否被覆盖
   • total_covered = 0：被覆盖的非免费实体数
   • covered_groups = set()：被覆盖实体所属的T_n集合
   • i = 0：当前遍历索引
3. 循环处理实体：
   • 若covered[i]为True，i +=1，跳过当前实体
   • 否则，取当前实体(s, e, g)，计算最优窗口的结束时间R = e，起始时间L = max(e - M, 0)（确保窗口时长≤M）
   • 用二分查找在starts中找到最大的索引j，使得starts[j] ≤ R（因为实体按end排序，后续实体的end ≥ e ≥ L，只要start ≤ R就会被窗口覆盖）
   • 标记i到j的所有实体为已覆盖，更新total_covered += (j - i + 1)，并将这些实体的group加入covered_groups
   • 设置i = j + 1，继续处理下一批未覆盖的实体

结果计算 #

• 最大总实体数 = total_free + total_covered
• 对应T_n集合 = free_groups.union(covered_groups)

规则适配（针对示例特殊情况） #

如果实际需求是仅选择单个停留窗口（如示例1仅选一个窗口），只需修改核心算法：遍历所有可能的最优窗口候选，计算每个窗口覆盖的非免费实体数，加上对应T_n的免费实体数，取最大值：

1. 对每个非免费实体，生成候选窗口[max(e-M,0), e]
2. 用二分查找计算该窗口覆盖的实体数，加上该实体所属T_n的免费实体数
3. 同时单独计算所有免费实体总数（若允许不选窗口仅拿免费实体）
4. 取所有候选中的最大值，对应的T_n为窗口覆盖实体所属的T_n加上有免费实体的T_n

示例验证（示例1） #

• T0的非免费实体排序后：[[0,2], [2,4], [1,8], [7,8], [5,9]]
• 处理到第一个未覆盖实体[0,2]，窗口为[0,2]，二分找到最后一个start ≤2的实体是[1,8]（索引2），覆盖3个实体，total_covered=3
• 免费实体数total_free=1，总实体数3+1=4，对应T_n={0}，与示例1一致

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