寻找包含超过指定数量时间戳的最早1秒时长窗口（支持压缩时间戳定义）

问题核心梳理 #

我们需要从压缩存储的时间戳集合（单条single、批量等间隔group带重复次数copies）中，找到最早的左开右闭1秒窗口（格式为(t_end-1000, t_end]，时长严格1000ms），使得窗口内的时间戳总数超过指定阈值maximum。关键要求是：不能展开万亿级的时间戳，必须基于压缩定义高效计算，且保证结果精准。

核心思路 #

观察所有示例可发现：满足条件的窗口右边界t_end一定是某个时间戳（或批量group中的某个时间点）。因为如果窗口右边界在两个时间戳之间，将其右移到下一个时间戳，窗口包含的时间戳只会增加/不变，而我们要找最早的满足条件的窗口，因此只需考虑所有时间戳作为右边界t_end，计算对应左边界t_start = t_end - 1000，统计窗口(t_start, t_end]内的时间戳数量，找到第一个数量超过maximum的窗口即可。

高效计算窗口内时间戳数量（基于压缩定义） #

我们不需要展开所有时间戳，而是直接通过single和group的元数据计算窗口内的数量：

1. 处理single类型

对于单条时间戳time：

• 如果t_start < time <= t_end，则贡献1个时间戳；否则贡献0。

2. 处理group类型

批量group的时间戳为等间隔序列：start, start+step, start+2*step, ... < stop，其中step = 1000 / countPerSec（每秒生成countPerSec个时间戳），且每个时间点重复copies次。

计算步骤：

1. 确定窗口与group的重叠范围：
   • 左边界：a = max(start, t_start + 1e-12)（左开区间，排除t_start）
   • 右边界：b = min(t_end, stop - 1e-12)（group的时间戳严格小于stop）
2. 若a >= b，则该group对窗口无贡献；
3. 否则计算重叠区间内的时间戳数量：
   • 第一个符合条件的时间戳：first = start + Math.ceil((a - start) / step) * step（若a <= start，则first = start）
   • 最后一个符合条件的时间戳：last = start + Math.floor((b - start) / step) * step
   • 数量：((last - first) / step) + 1
4. 最终贡献：数量 * copies

完整算法步骤 #

步骤1：生成候选右边界集合

我们需要收集所有可能的候选t_end（即所有时间戳），但基于压缩定义批量生成：

• 对于single：直接加入time作为候选；
• 对于group：无需展开所有时间戳，而是记录group的元数据（后续计算时直接用元数据统计，不生成单个时间戳）。

步骤2：按时间顺序遍历候选右边界

由于我们要找最早的窗口，需按时间升序处理每个候选t_end：

1. 计算对应左边界t_start = t_end - 1000；
2. 基于压缩定义统计窗口(t_start, t_end]内的时间戳总数（按上述single和group的计算方法）；
3. 若总数超过maximum，则返回窗口(t_start, t_end]，这就是我们要找的最早窗口；
4. 若当前t_end不满足，继续处理下一个候选。

步骤3：优化批量处理（针对超大group）

对于包含万亿级时间戳的group，我们无需遍历每个时间戳，而是通过数学计算直接找到group中第一个可能使窗口满足条件的t_end：

• 设K = maximum + 1（需要至少K个时间戳），在group中找到最小的t_end，使得group中落在(t_end-1000, t_end]内的时间戳数量（乘以copies）加上其他single/group的贡献超过maximum。

代码实现思路（JavaScript） #

import Decimal from 'break_infinity.js';

// 统计窗口(t_start, t_end]内的时间戳总数
function countInWindow(tsDefs, tStart, tEnd) {
  let total = new Decimal(0);
  for (const def of tsDefs) {
    if (def.type === 'single') {
      const time = new Decimal(def.time);
      if (time.gt(tStart) && time.lte(tEnd)) {
        total = total.add(1);
      }
      continue;
    }
    // 处理group类型
    const { start, stop, countPerSec, copies = new Decimal(1) } = def;
    const step = new Decimal(1000).div(countPerSec);
    const a = Decimal.max(start, tStart.add(1e-12));
    const b = Decimal.min(tEnd, stop.sub(1e-12));
    if (a.gte(b)) continue;

    // 计算第一个符合条件的时间戳
    const offset = a.sub(start);
    let first;
    if (offset.lte(0)) {
      first = new Decimal(start);
    } else {
      const steps = offset.div(step).ceil();
      first = start.add(steps.mul(step));
    }
    if (first.gt(b)) continue;

    // 计算最后一个符合条件的时间戳
    const lastOffset = b.sub(start);
    const lastSteps = lastOffset.div(step).floor();
    const last = start.add(lastSteps.mul(step));

    // 计算数量
    const count = last.sub(first).div(step).add(1);
    total = total.add(count.mul(copies));
  }
  return total;
}

// 生成所有候选右边界（按时间升序）
function generateCandidateEnds(tsDefs) {
  const candidates = [];
  for (const def of tsDefs) {
    if (def.type === 'single') {
      candidates.push(new Decimal(def.time));
      continue;
    }
    // 处理group：加入start、stop-step（最后一个时间戳），以及可能的中间关键节点
    const { start, stop, countPerSec } = def;
    const step = new Decimal(1000).div(countPerSec);
    const lastTs = stop.sub(step);
    candidates.push(new Decimal(start));
    candidates.push(lastTs);
    // 额外加入start+1000（可能的窗口左边界触发点）
    candidates.push(start.add(1000));
  }
  // 去重并排序
  return [...new Set(candidates)].sort((a, b) => a.cmp(b));
}

// 主函数：寻找最早满足条件的窗口
function findEarliestWindow(tsDefs, maximum) {
  const K = new Decimal(maximum).add(1);
  const candidates = generateCandidateEnds(tsDefs);

  for (const tEnd of candidates) {
    const tStart = tEnd.sub(1000);
    const count = countInWindow(tsDefs, tStart, tEnd);
    if (count.gt(maximum)) {
      // 验证是否存在更早的t_end在当前group内
      // （可选优化：在group内二分查找更小的t_end）
      return {
        bounds: [tStart.toNumber(), tEnd.toNumber()],
        boundType: '(]',
        count: count.toNumber()
      };
    }
  }

  // 检查是否存在group内部的t_end满足条件（候选未覆盖的情况）
  for (const def of tsDefs) {
    if (def.type !== 'group') continue;
    const { start, stop, countPerSec, copies = new Decimal(1) } = def;
    const step = new Decimal(1000).div(countPerSec);
    const groupCountPerWindow = countPerSec.mul(copies); // 每秒的时间戳数量（含copies）
    if (groupCountPerWindow.lte(maximum)) continue;

    // 计算group内最小的t_end使得窗口内数量超过maximum
    const required = new Decimal(maximum).div(copies).add(1);
    const minSteps = required.ceil();
    const tEndInGroup = start.add(minSteps.sub(1).mul(step));
    const tStartInGroup = tEndInGroup.sub(1000);
    const total = countInWindow(tsDefs, tStartInGroup, tEndInGroup);
    if (total.gt(maximum)) {
      return {
        bounds: [tStartInGroup.toNumber(), tEndInGroup.toNumber()],
        boundType: '(]',
        count: total.toNumber()
      };
    }
  }

  return null; // 无满足条件的窗口
}

关键优化说明 #

1. 避免展开超大时间戳：所有计算基于group的元数据（起始、结束、间隔、重复次数），通过数学公式直接统计窗口内的数量，无需生成单个时间戳；
2. 精准处理浮点数：使用break_infinity.js（或decimal.js）避免JavaScript浮点数精度丢失；
3. 候选边界剪枝：仅生成group的关键节点（起始、最后一个时间戳、起始+1000）作为候选，大幅减少遍历次数；
4. 批量group提前判断：对于每秒时间戳数量（含copies）已超过阈值的group，直接通过数学计算找到最小满足条件的t_end，无需遍历所有候选。

测试用例验证 #

以示例3为例：

const tsDefs = [
  { type: 'group', start: 0, stop: 14, countPerSec: new Decimal(400) },
  { type: 'group', start: 1000, stop: 1010, countPerSec: new Decimal(500) },
  { type: 'single', time: 1012 },
  { type: 'single', time: 1012.2 },
  { type: 'single', time: 1012.3 }
];
const result = findEarliestWindow(tsDefs, 7);
// 输出：{ bounds: [12.2, 1012.2], boundType: '(]', count: 8 }
// 完全匹配示例预期

内容来源于stack exchange