题目内容

运维平台按时间顺序上报一批告警 events。每一项是 [timestamp, alarmType]：

• timestamp：告警发生时刻
• alarmType：告警类型

保证 timestamp 非降序（可相等）。

平台要对每种类型独立做限流，规则如下（按上报顺序逐条处理）：

处理某条告警，设其时刻为 $t$、类型为 $type$。只看该类型里此前已被保留的告警，统计其中时刻落在半开区间 $(t-\textit{window},\, t]$ 内的条数：

• 若该数目已经达到 limit，则本条抑制（不保留）
• 否则本条保留

说明：区间左开右闭，即时刻等于 $t-\textit{window}$ 的历史告警不计入窗口；时刻等于 $t$ 的、已先处理并保留的同刻告警计入。

请返回最终保留的告警总条数。

请实现：

countKeptAlarms(events: int[][], window: int, limit: int) -> int

输入描述

三行：

• 第一行：二维数组 events，形如 [[1, 1], [2, 1], [10, 1]]
• 第二行：整数 window（窗口长度）
• 第三行：整数 limit（同类型窗口内最多保留条数）

约束：

• $0 \le \texttt{events.length} \le 10^5$
• $0 \le \texttt{timestamp}_i \le 10^9$，非降序
• $1 \le \texttt{alarmType}_i \le 10^5$
• $0 \le \textit{window} \le 10^9$
• $1 \le \textit{limit} \le 10^5$

输出描述

一个整数：保留条数。

样例1

输入：

[[1, 1], [2, 1], [3, 1], [10, 1]]
5
2

输出：

3

说明：

均为类型 1，window=5，limit=2。

• 时刻 $1$、$2$：窗口内已保留不足 $2$，均保留
• 时刻 $3$：窗口 $(3-5,3]=(0,3]$ 内已保留时刻 $1$、$2$ 共 $2$ 条，抑制
• 时刻 $10$：窗口 $(5,10]$ 内此前保留的都不在其中，可再保留

共保留 $3$ 条。

样例2

输入：

[[0, 2], [0, 2], [0, 3]]
0
1

输出：

2

说明：

window=0 时窗口为 $(t,t]$，不含更早历史；但同一时刻已保留的仍计数。类型 2 同刻第一条保留、第二条达 limit=1 被抑制；类型 3 保留。共 $2$ 条。

样例3

输入：

[]
10
3

输出：

0