Voleon 面试题 #1 —— 最少开机覆盖滑雪道（贪心/区间覆盖）– voleon 面经 – VO 辅助 —— 代面试

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

1. N = 2, machines [(0,1), (1,1), (2,1)] → 1
   Turn on the middle machine at index 1 to cover the entire slope.
2. N = 3, machines [(0,2)] → -1
   The only machine at index 0 cannot cover the entire slope.
3. 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.

简单总结（思路）

把每台机器 (i, r) 转成区间 [max(0, i−r), min(N, i+r)]，问题变成：用 最少区间 覆盖 [0, N]。
按区间起点升序排序，做 贪心跳跃 ：在当前可达的起点范围内选择能把 右端点延伸最远 的区间，计数 +1，更新当前覆盖到的最远位置；若某一步没有区间能推进，返回 -1。
时间复杂度 O(M log M)（排序），空间 O(1)（不计区间存储）。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Voleon、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。