Loading page…
Practice problem · medium
A monitoring system records alerts. An alert is firing from its start second to its end second, and both of those seconds count. Many alerts can fire at once.
On-call engineers ask the dashboard questions of the form: how many alerts were firing at second t? You get all the alerts and a list of questions, and you answer each one.
Write firing_counts(alerts, queries).
alerts[i] = [start, end], with start <= end. The alert is firing at every second from start to end, including both.queries[j], count the alerts with start <= queries[j] <= end.Input: alerts = [[1, 5], [2, 3], [4, 9], [8, 10]], queries = [3, 6, 9, 11]
Output: [2, 1, 2, 0]Sort the starts and the ends on their own: starts 1, 2, 4, 8 and ends 3, 5, 9, 10. For a question t, the number of alerts that have started is the count of starts at most t. The number that have already ended is the count of ends less than t. The difference is how many are firing.
| Question t | Starts ≤ t | Ends < t | Firing |
|---|---|---|---|
| 3 | 2 | 0 | 2 |
| 6 | 3 | 2 | 1 |
| 9 | 4 | 2 | 2 |
| 11 | 4 | 4 | 0 |
Input: alerts = [[1, 5]], queries = [5]
Output: [1]The alert includes its last second, so it is still firing at second 5.
Input: alerts = [[1, 10], [2, 3]], queries = [5]
Output: [1]At second 5, the long alert is firing and the short one has ended.
0 ≤ alerts.length ≤ 100,0000 ≤ queries.length ≤ 100,0000 ≤ start ≤ end ≤ 1,000,000,000, and 0 ≤ queries[j] ≤ 1,000,000,000 (seconds)Checking every alert for every question costs about n × q, which is 10^10 at n = q = 100,000. Sorting the starts and the ends once costs n log n, and each question then costs a binary search, log n.
firing_counts · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.