Total Alarm Time
EasyIntervalsFree
Problem
A motion sensor sets off an alarm. Each trigger at second t makes the alarm ring during the half-open window [t, t + duration). If the sensor fires again while the alarm is already ringing, the ringing does not stack: it simply continues until duration seconds after the latest trigger.
Given the trigger times triggers in non-decreasing order and the duration, return the total number of seconds the alarm rings.
Example 1
- Input:
- triggers = [1, 4], duration = 2
- Output:
- 4
It rings during [1, 3) and [4, 6): 2 + 2 = 4 seconds.
Example 2
- Input:
- triggers = [1, 2], duration = 2
- Output:
- 3
The windows [1, 3) and [2, 4) overlap and together cover [1, 4).
Constraints
- 0 ≤ triggers.length ≤ 10^5
- 0 ≤ triggers[i] ≤ 10^9, sorted non-decreasing
- 0 ≤ duration ≤ 10^6
Hint
Show the first hint
Each trigger contributes at most duration seconds. When does it contribute less?
Walkthrough
How to approach it
01Clarify before coding
- Are the triggers sorted? Yes, non-decreasing, and duplicates are possible.
- Can duration be 0? Yes; then the alarm never rings.
- Can the list be empty? Yes → 0 seconds.
02Brute force
Mark every ringing second in a set (or boolean array) and count the marks.
Cost: O(n · duration) time and up to O(n · duration) memory: with duration = 10^6 and n = 10^5 that is 10^11 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.