Loading page…
Practice problem · medium
A social app hosts live shows. Each show is on air from a start second to an end second, and both of those seconds are part of the show. The app can send a notification at any second. A notification reaches every show that is on air at that second.
The team wants every show to receive a notification while it is on air, and wants to send as few notifications as possible.
Write fewest_pings(shows).
shows[i] = [start, end], with start <= end. The show is on air at every second from start to end, including both.t reaches the shows with start <= t <= end.Input: shows = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2Sort by end. Send a notification at the end of the first show that has not been reached. It reaches every show that has started by then.
| Show | Last notification | Reached? | Action |
|---|---|---|---|
| [1, 6] | none | no | send at 6 |
| [2, 8] | 6 | yes, 2 ≤ 6 | none |
| [7, 12] | 6 | no, 7 > 6 | send at 12 |
| [10, 16] | 12 | yes, 10 ≤ 12 | none |
Two notifications reach every show.
Input: shows = [[1, 2], [2, 3]]
Output: 1A notification at second 2 reaches both shows, because second 2 is part of both.
Input: shows = [[1, 10], [2, 3], [4, 5]]
Output: 2The shows [2, 3] and [4, 5] do not share a second, so they need two notifications. Both notifications also reach the long show.
0 ≤ shows.length ≤ 100,0000 ≤ start ≤ end ≤ 1,000,000,000 (seconds)Trying every set of send times is exponential. Even checking every pair of shows costs about n × n, which is 10^10 at n = 100,000. Sorting by end costs n log n, and one pass costs n.
fewest_pings · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.