Loading page…
Practice problem · medium
An online store lists its sale windows on a banner. Each window is a range of minutes [start, end], including both ends. Some windows lie completely inside a longer window, so showing them adds nothing.
The team wants to drop every window that is covered by another one. Count the windows that are left.
Write slots_not_covered(slots).
slots[i] = [start, end], with start <= end. No two slots are identical.[a, b] is covered by another slot [c, d] when c <= a and b <= d.Input: slots = [[1, 4], [3, 6], [2, 8]]
Output: 2Sort by start, and for equal starts put the longer slot first. Then keep the furthest end seen so far. A slot whose end does not pass it is covered.
| Slot | Furthest end before | Covered? | Count |
|---|---|---|---|
| [1, 4] | none | no | 1 |
| [2, 8] | 4 | no: 8 > 4 | 2 |
| [3, 6] | 8 | yes: 6 ≤ 8 | 2 |
The slot [3, 6] lies inside [2, 8], so 2 slots are left.
Input: slots = [[1, 10], [2, 3], [4, 5]]
Output: 1Both small slots lie inside [1, 10].
Input: slots = [[1, 2], [1, 4]]
Output: 1The two slots start together. [1, 2] lies inside [1, 4], so only [1, 4] is left.
0 ≤ slots.length ≤ 100,000 (sale windows)0 ≤ start ≤ end ≤ 10,000,000 (minutes)Checking each slot against every other slot costs about n × n, which is 10^10 at n = 100,000. Sorting costs n log n, and one pass after it costs n.
slots_not_covered · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.