Find and Merge Camera Alert Intervals
Company: Verkada
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given surveillance camera readings as time-series data.
Each reading is a pair `(timestamp, value)`, sorted by `timestamp`. A camera is considered to be in an alert state whenever `value > threshold`.
Implement the following:
1. **Single camera:** Given one camera's readings and a threshold, return all maximal alert intervals `[start, end]` based on the recorded timestamps. An interval starts when the readings transition from `value <= threshold` to `value > threshold`, and it ends at the last recorded timestamp before the alert condition stops. If the camera is still above the threshold at the end of the input, close the interval at the final timestamp.
2. **Multiple cameras:** Given alert intervals from multiple cameras, merge them into a single list of non-overlapping intervals representing any time range during which at least one camera was in alert.
Assumptions:
- Timestamps are integers.
- Input readings for each camera are already sorted.
- When merging intervals, treat touching intervals as overlapping; for example, `[1, 3]` and `[3, 5]` should become `[1, 5]`.
Discuss the algorithm, edge cases, and time complexity.
Quick Answer: This question evaluates understanding of time-series processing, interval detection, and interval-merging algorithms, including handling thresholds, touching intervals, and open-ended alerts.