Alert Cluster Coalesce
An on-call dashboard receives a flood of alerts during an incident. Each alert has a timestamp (in seconds). To stop paging fatigue, the dashboard groups any alerts within w seconds of the previous one into the same cluster. Count how many clusters the dashboard will show.
Problem
Given a sorted ascending array of alert timestamps timestamps and an integer w, return the number of clusters produced when two consecutive alerts merge into the same cluster iff their gap is at most w.
Input
An integer n (0 ≤ n ≤ 10^5), the sorted timestamps array (each in [0, 10^9]), and an integer w (0 ≤ w ≤ 10^9).
Output
A single integer — the number of clusters.
Constraints
- 0 ≤ n ≤ 100,000
- Array is sorted ascending
- Two same-second alerts are always in the same cluster (gap = 0 ≤ w)
- Empty array → 0 clusters
Examples
Example 1
Input
timestamps = [0, 1, 2, 10, 11, 100], w = 3
Output
3
[0,1,2] one cluster (gaps 1,1). [10,11] another. [100] another.
Example 2
Input
timestamps = [], w = 5
Output
0
Empty → no clusters.