Ski season is approaching! You work at a ski resort and must ensure the slopes are fully covered with snow.
You have a slope with indices from 0...N, and a collection of snow-making machines installed along the slope.
Each machine is a tuple (index, range) meaning the machine sits at index and can cover the slope with snow up to range indices away (i.e., it covers from index - range to index + range).
Goal: Turn on the smallest number of machines so the entire slope is covered.
If it is impossible to cover the whole slope, return -1.
Function: Given N and a list of machines [(i, r), ...], return the minimum number of machines needed, or -1.
Examples
N = 2, machines[(0,1), (1,1), (2,1)]→1
Turn on the middle machine at index 1 to cover the entire slope.N = 3, machines[(0,2)]→-1
The only machine at index 0 cannot cover the entire slope.N = 5, machines[(0,2), (1,1), (3,1), (4,1)]→2
Use machine at 0 or 1 to cover up to 2; machine at 4 covers 3–5.
Brief Summary (Approach)
Convert each machine (i, r) to interval [max(0, i−r), min(N, i+r)]. Then solve the classic minimum interval cover for [0, N]: sort by start, and greedily pick, among intervals starting at or before the current end, the one with the farthest reach. Count selections; if you can’t extend coverage at some step, return -1. Runs in O(M log M) time due to sorting.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Voleon, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
