解题思路
数据范围 n≤15,可直接 枚举子集(位掩码 0…2n−1):
- 将
timestamps 排序,便于按索引取元素;
- 对每个
mask,取出被选中的时间戳列表 picked;
- 双重循环检查任意两元素之差是否 ≥
minInterval;
- 合法则答案 +1(空集
mask=0 自动合法)。
题目内容
在微服务网关中,为了防止某个用户短时间内发送过多请求,通常会采用最小请求间隔限流策略:即同一个用户相邻两个请求的时间戳之差必须大于等于 minInterval 秒。例如,若 minInterval=2,则请求时间戳为 1 和 3 可以同时通过(差为 2),但 1 和 2 不能同时通过(差为 1)。
现有一批属于同一用户的请求,每个请求带有一个时间戳(单位:秒,整数)。网关需要从这批请求中挑选一部分放行,使得任意两个被放行的请求时间差都 ≥minInterval。请你计算一共有多少种合法的放行方案(包括空集)。
例如,请求时间戳为 [1,3,4],minInterval=2,则合法的放行方案有:[]、[1]、[3]、[4]、[1,3]、[1,4],共 6 种(注意 [3,4] 非法,因为差为 1<2)。
输入描述
输入格式
- int[] timestamps:整数数组,表示每个请求的时间戳(可能乱序,无重复)。
- int minInterval:最小允许的请求间隔(秒),minInterval≥1。
输出描述
数据规模
- 1≤timestamps.length≤15
- 时间戳取值范围:0≤timestamp≤109
- minInterval 为正整数
样例1
输入
[1,2,4],2
输出
6
说明
合法方案:[]、[1]、[2]、[4]、[1,4]、[2,4],共 6 种
样例2
输入
[10],5
输出
2
说明
合法方案:[]、[10],共 2 种