Loading page…
Practice problem · medium
A monitoring system receives outage reports from many probes. Each report is a window [start, end] in seconds during which one probe saw the service down. Reports come in any order and often overlap.
The incident page should show each outage once. Windows that overlap, or touch at one second, are the same outage and must be joined into one window.
Write merge_slots(slots).
slots[i] = [start, end], with start <= end. A slot covers every second from start to end, including both.Input: slots = [[8, 10], [1, 3], [2, 6], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]Sort by start, then keep one open slot. Each next slot either joins it, when its start is at or before the open end, or closes it and opens a new one.
| Next slot | Open slot | Action |
|---|---|---|
| [1, 3] | none | open [1, 3] |
| [2, 6] | [1, 3] | 2 ≤ 3: join, end becomes 6 |
| [8, 10] | [1, 6] | 8 > 6: close, open [8, 10] |
| [15, 18] | [8, 10] | 15 > 10: close, open [15, 18] |
Input: slots = [[1, 3], [3, 5]]
Output: [[1, 5]]Both slots include second 3, so they are one outage.
Input: slots = [[1, 10], [2, 4]]
Output: [[1, 10]]The second slot lies inside the first, so it adds nothing.
0 ≤ slots.length ≤ 100,000 (reports)0 ≤ start ≤ end ≤ 1,000,000,000 (seconds)Looking for any two slots that overlap, joining them, and starting again can cost about n × n for each join. That is far too slow at n = 100,000. Sorting by start costs n log n, and one pass after it costs n.
merge_slots · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.