1. 项目概述：从一道机试题看算法思维

最近在帮几个准备华为OD机试的朋友做模拟训练，发现“路灯照明问题”这道题出现的频率相当高，几乎成了必刷的经典。这道题本身并不复杂，但它巧妙地融合了 区间覆盖 和 贪心算法 的核心思想，是检验候选人基础算法能力和代码实现功底的绝佳试金石。很多朋友第一次看到题目描述时，会觉得“这不就是个简单计算吗？”，但一上手写代码，就会在边界条件、精度处理和最优解证明上栽跟头。今天，我就结合自己当年备考和后来担任面试官的经验，用C++、Java、JavaScript和Python四种语言，把这道题从问题本质到代码实现的每一个细节，掰开揉碎了讲清楚。无论你是正在备战机试，还是想巩固一下基础算法，相信这篇深度解析都能给你带来实实在在的帮助。

简单来说，路灯照明问题可以抽象成这样：在一条一维的道路上，给定每个路灯的位置和照明半径，求最少需要打开多少盏灯，才能让整条道路都被灯光覆盖。这听起来很像我们小时候做的“用最少的点覆盖整个区间”的数学题，但在编程实现时，我们需要处理路灯位置无序、照明半径可能不同、区间可能重叠等一系列现实情况。这道题的价值在于，它迫使你跳出“模拟”的思维定式，去思考更高效的贪心策略，并且对代码的健壮性提出了很高要求。接下来，我们就从问题建模开始，一步步拆解。

2. 问题建模与核心思路拆解

2.1 问题重述与数学抽象

我们先来严格定义一下题目。通常，题目会给出以下输入：

1. 一条道路的长度 L （例如100米）。
2. 一个数组 lights ，包含 N 个路灯的信息。每个路灯信息通常是一个二元组 (position, radius) ，表示路灯在道路上的位置（距离起点0点的距离）及其照明半径。

目标 ：选择打开一部分路灯，使得整条道路 [0, L] 的每一个点都被至少一盏打开的灯照亮，并且要求打开的路灯数量尽可能少。

约束条件 ：

• 路灯的照明范围是以其位置为中心，向左右各延伸 radius 距离的区间。即，位于 pos ，半径为 r 的路灯，其照明区间为 [pos - r, pos + r] 。
• 我们需要的是覆盖连续区间 [0, L] ，而不是离散的点。
• 路灯可以安装在 [0, L] 区间之外吗？这是关键！ 经典且严谨的模型是：路灯只能安装在道路区间 [0, L] 上 。但有些题目变体会允许路灯安装在区间外，这时照明区间的左端点可能小于0，右端点可能大于L。我们的解析基于经典模型，并会讨论变体。

输出 ：一个整数，表示最少需要打开的路灯数量。如果无法覆盖整条道路，则返回 -1 或特定标识。

2.2 贪心算法思路详解

为什么这道题适合用贪心算法？因为它的最优子结构非常明显：为了用最少的灯覆盖从起点开始的道路，我们每一步都“贪心地”选择那个能覆盖当前未被覆盖的起点（我们称之为 currentPos ），并且能覆盖得最远（即右端点最大）的路灯。

让我们把这个思路步骤化：

1. 数据预处理 ：将每个路灯的 (position, radius) 信息，转换为其能照亮的实际区间 [left, right] ，其中 left = position - radius , right = position + radius 。同时，我们需要处理区间与道路 [0, L] 的交集，因为路灯照亮的道路外部分是无用的。所以，有效的照明区间是 [max(0, left), min(L, right)] 。如果某个路灯处理后的区间长度 <= 0 （即 right <= 0 或 left >= L ），说明它完全照不到道路上，可以直接丢弃。

2. 区间排序 ：将所有有效区间按照 左端点 left 从小到大 进行排序。如果左端点相同，理论上可以按照右端点从大到小排序，这样我们在遍历时能优先选择覆盖更远的，但这不是必须的，核心逻辑能处理。

3. 贪心选择 ：

   • 初始化 currentPos = 0 （当前需要被覆盖的起点）， count = 0 （已选择的路灯数）， i = 0 （遍历区间的索引）。
   • 在 currentPos < L 的条件下循环： a. 从 i 开始，遍历所有 左端点 left 小于等于 currentPos 的区间。因为只有左端点不超过 currentPos ，这个灯才能接上之前覆盖的区域。 b. 在这些可选的区间中，记录下它们中最大的 右端点 right ，记为 maxRight 。选择这个能覆盖到最远位置的灯。 c. 如果找不到任何一个左端点 <= currentPos 的区间（即 maxRight 没有被更新，或者 i 已经越界），说明出现了“断层”，无法继续覆盖，直接返回 -1。 d. 否则，说明我们成功选择了一盏灯。 count++ ，然后将 currentPos 更新为 maxRight （因为这盏灯已经覆盖到了 maxRight ，下一盏灯需要从 maxRight 开始接上）。 e. 如果更新后的 currentPos >= L ，说明已经覆盖完成，跳出循环。 f. 继续下一轮选择。

注意 ：这里有一个极其关键的细节，也是很多初学者出错的地方。在步骤a中，我们寻找的是 left <= currentPos 的灯，而不是 left <= currentPos 且 right > currentPos 。因为 right 可能等于 currentPos ，但这盏灯依然没有提供新的覆盖（它的右端点没有超过当前点），选择它是无用的。所以，更严谨的说法是：在寻找 maxRight 时，我们只考虑那些 left <= currentPos 且 right > currentPos 的区间。但在实现中，由于我们会记录 maxRight ，如果所有可选区间的 right 都 <= currentPos ，那么 maxRight 就不会超过 currentPos ，我们就能在步骤c中检测到失败。两种理解等价，但后一种更助于理解“断层”的本质。

2.3 算法正确性简要证明（为什么贪心是有效的？）

贪心算法不是瞎猜，我们需要心里有底它为什么能得到最优解。对于区间覆盖问题，一个常见的证明思路是“替换法”。

假设我们的贪心算法选择了一系列区间： I1, I2, ..., Ik 。 假设存在一个最优解，它选择的一系列区间是： J1, J2, ..., Jm ，并且 m < k （即最优解用的灯更少）。

我们尝试比较这两个解。贪心算法在选择 I1 时，是在所有左端点能覆盖起点0的区间中，选了右端点最大的。那么，最优解中的 J1 ，其左端点也必须能覆盖0，但其右端点 right(J1) 一定 不大于 right(I1) 。因为如果 right(J1) > right(I1) ，贪心算法当时就会选它了。

既然 right(J1) <= right(I1) ，那么在用 J1 覆盖后，剩余需要覆盖的起点是 right(J1) 。而贪心算法用 I1 覆盖后，剩余起点是 right(I1) ，并且 right(I1) >= right(J1) 。这意味着，贪心算法面临的剩余问题（覆盖 [right(I1), L] ）比最优解面临的剩余问题（覆盖 [right(J1), L] ） 更困难 （因为起点更靠右）。

现在，我们看第二步。贪心算法在 right(I1) 的基础上，又用同样的策略选择了能覆盖最远的 I2 。对于最优解，它需要在 right(J1) 的基础上选择 J2 。由于 right(I1) >= right(J1) ，所以 J2 的左端点必须 <= right(J1) <= right(I1) ，因此 J2 也在贪心算法第二步的可选范围内。根据贪心策略， I2 是所有可选区间中右端点最大的，所以 right(I2) >= right(J2) 。

如此递推下去，我们会发现，贪心解每一步覆盖的终点都不比最优解差。如果最优解用了 m 盏灯覆盖到了 L ，那么贪心解用了 k 盏灯也一定能覆盖到 L ，并且由于每一步都“贪心”地覆盖了最远， k 不可能大于 m （实际上，如果 k > m ，我们可以用贪心解的前 m 步与最优解比较，推导出矛盾）。因此，贪心解就是最优解。

这个证明过程稍微有点绕，但理解其核心思想很重要： 贪心算法每一步的局部最优选择，保证了后续问题的规模不会比任何其他解面临的更差，从而导向全局最优 。

3. 多语言代码实现与细节剖析

理解了算法，接下来就是“手上有活”的环节了。我将用四种语言分别实现，并重点讲解每种语言实现时的特有细节和易错点。我们假设输入格式为：道路长度 L ，以及一个列表/数组 lights ，其中每个元素是 [position, radius] 。

3.1 C++ 实现：效率与控制的艺术

C++的实现注重效率和精细控制，特别是在处理浮点数比较和区间排序时。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Interval {
    double left;
    double right;
    // 按左端点排序
    bool operator<(const Interval& other) const {
        // 优先按左端点排序，左端点相同按右端点大的排前面（贪心友好）
        if (fabs(left - other.left) < 1e-9) {
            return right > other.right;
        }
        return left < other.left;
    }
};

int minLights(double L, vector<vector<double>>& lights) {
    vector<Interval> intervals;
    
    // 1. 预处理，构建有效区间
    for (const auto& light : lights) {
        double pos = light[0];
        double r = light[1];
        double left = pos - r;
        double right = pos + r;
        // 取与道路[0, L]的交集
        left = max(0.0, left);
        right = min(L, right);
        if (left <= right) { // 有效区间
            intervals.push_back({left, right});
        }
    }
    
    // 2. 按左端点排序
    sort(intervals.begin(), intervals.end());
    
    int n = intervals.size();
    int count = 0;
    double currentPos = 0.0;
    int i = 0;
    
    // 3. 贪心选择
    while (currentPos < L) {
        double maxRight = currentPos; // 初始化为当前点，用于判断是否找到新区间
        int chosenIndex = -1;
        
        // 遍历所有左端点不超过currentPos的区间，找右端点最大的
        while (i < n && intervals[i].left <= currentPos + 1e-9) { // 浮点数容差
            if (intervals[i].right > maxRight) {
                maxRight = intervals[i].right;
                chosenIndex = i; // 记录，但非必须
            }
            i++;
        }
        
        // 如果maxRight没有被更新（即没有找到能延伸覆盖的灯）
        if (fabs(maxRight - currentPos) < 1e-9) {
            return -1; // 无法覆盖
        }
        
        // 选择这盏灯
        count++;
        currentPos = maxRight;
        
        // 一个小优化：如果已经覆盖完成，提前退出
        if (currentPos >= L - 1e-9) {
            break;
        }
        
        // 注意：这里不需要将i回退。因为下一次循环，我们需要找的是左端点<=新currentPos的灯。
        // 由于区间已排序，且我们之前的i已经遍历到了左端点<=旧currentPos的所有灯，
        // 而新currentPos >= 旧currentPos，所以接下来需要的灯的左端点可能更大，i继续向前即可。
        // 但如果新currentPos比某些之前跳过的灯的右端点还小，那些灯可能还有用吗？
        // 不会，因为那些被跳过的灯，其左端点虽然<=旧currentPos，但右端点<=maxRight（否则就会被选中）。
        // 所以它们的右端点都<=新currentPos，对后续覆盖没有贡献。
    }
    
    return count;
}

int main() {
    // 示例
    double L = 100;
    vector<vector<double>> lights = {{20, 20}, {40, 10}, {60, 15}, {80, 20}};
    int result = minLights(L, lights);
    cout << "最少需要路灯数量: " << result << endl; // 输出应为2 (选择第1盏和第4盏)
    return 0;
}

C++实现要点与避坑指南：

1. 浮点数精度处理 ：这是最大的坑！路灯位置和半径可能是浮点数。在比较 left <= currentPos 和判断 maxRight 是否更新时，直接使用 == 或 > 可能因精度问题出错。必须使用一个极小的容差值（如 1e-9 ）。 fabs(a-b) < eps 判断相等， a > b + eps 判断大于。
2. 结构体与排序 ：自定义 Interval 结构体并重载 < 运算符，可以使 sort 更清晰。在排序时，如果左端点相同，让右端点大的排在前面，这是一个有益的优化，能让贪心遍历时更早遇到更优的候选。
3. 循环变量 i 的管理 ：这是贪心实现的核心技巧。 i 是全局向前推进的，不需要在每一轮选择后回退。为什么？假设本轮我们基于 currentPos 选择了区间 intervals[k] ，使得 currentPos 更新为 maxRight 。下一轮我们需要找左端点 <= maxRight 的区间。由于数组已排序，且 i 已经走到了第一个左端点 > old_currentPos 的区间位置。因为 maxRight >= old_currentPos ，所以下一轮需要的区间其左端点可能 >= old_currentPos ， i 从这个位置开始检查是正好的。那些左端点 <= old_currentPos 但右端点较小的区间，已经被遍历过且因为不够“远”而被淘汰了，它们对覆盖 maxRight 之后的区域没有帮助。
4. chosenIndex 的作用 ：代码中记录了 chosenIndex ，但在最终计算中并未使用。在实际题目中，如果要求输出具体选择了哪些灯，这个变量就派上用场了。

3.2 Java 实现：面向对象的清晰表达

Java的实现利用其面向对象的特性，代码结构清晰，易于理解。

import java.util.Arrays;
import java.util.Comparator;

public class StreetLightCoverage {
    
    static class Interval {
        double left;
        double right;
        Interval(double left, double right) {
            this.left = left;
            this.right = right;
        }
    }
    
    public static int minLights(double L, double[][] lights) {
        int n = lights.length;
        Interval[] intervals = new Interval[n];
        int validCount = 0;
        
        // 1. 预处理，构建有效区间
        for (double[] light : lights) {
            double pos = light[0];
            double r = light[1];
            double left = Math.max(0, pos - r);
            double right = Math.min(L, pos + r);
            if (left <= right) {
                intervals[validCount++] = new Interval(left, right);
            }
        }
        
        // 只保留有效区间
        intervals = Arrays.copyOf(intervals, validCount);
        
        // 2. 按左端点排序，左端点相同按右端点降序
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval a, Interval b) {
                if (Math.abs(a.left - b.left) < 1e-9) {
                    // 右端点大的排前面
                    return Double.compare(b.right, a.right);
                }
                return Double.compare(a.left, b.left);
            }
        });
        
        int count = 0;
        double currentPos = 0.0;
        int i = 0;
        double eps = 1e-9;
        
        // 3. 贪心选择
        while (currentPos < L - eps) {
            double maxRight = currentPos;
            int startIndex = i; // 记录本轮开始的位置，用于debug
            
            // 找左端点不超过currentPos的区间中，右端点最大的
            while (i < validCount && intervals[i].left <= currentPos + eps) {
                if (intervals[i].right > maxRight) {
                    maxRight = intervals[i].right;
                }
                i++;
            }
            
            // 如果没有找到能延伸覆盖的灯
            if (Math.abs(maxRight - currentPos) < eps) {
                return -1;
            }
            
            count++;
            currentPos = maxRight;
            
            // 覆盖完成检查
            if (currentPos >= L - eps) {
                break;
            }
            
            // 如果i没有前进，说明当前所有剩余区间的左端点都大于currentPos，无法继续
            if (i == startIndex) {
                // 这种情况理论上在上面的maxRight判断中已经捕获，这里加个防御性判断
                return -1;
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        double L = 100;
        double[][] lights = {{20, 20}, {40, 10}, {60, 15}, {80, 20}};
        int result = minLights(L, lights);
        System.out.println("最少需要路灯数量: " + result); // 输出 2
    }
}

Java实现要点与避坑指南：

1. Comparator的使用 ：Java中对自定义对象数组排序，需要传入 Comparator 。这里我们实现了按左端点升序，左端点相同时按右端点降序的逻辑。注意 Double.compare(b.right, a.right) 实现了降序。
2. 数组拷贝 ：预处理后，我们可能丢弃无效区间。使用 Arrays.copyOf 可以创建一个新的紧凑数组，避免在后续遍历中判断 null 。
3. 浮点数精度 ：和C++一样，使用 eps = 1e-9 进行浮点数比较。 Math.abs(a-b) < eps 。
4. 防御性编程 ：在 while 循环后增加了 if (i == startIndex) 的判断。虽然在正确的逻辑下， maxRight 未更新已经意味着失败，但多加一层检查可以使逻辑更健壮，防止在特殊边界条件下（如所有区间左端点都大于0）陷入死循环或错误。

3.3 JavaScript 实现：灵活与动态的脚本语言

JavaScript在算法题中越来越常见，其动态类型和函数式特性可以写出非常简洁的代码。

function minLights(L, lights) {
    const eps = 1e-9;
    
    // 1. 预处理，构建有效区间数组
    const intervals = [];
    for (const [pos, r] of lights) {
        const left = Math.max(0, pos - r);
        const right = Math.min(L, pos + r);
        if (left <= right + eps) { // 考虑浮点误差
            intervals.push({ left, right });
        }
    }
    
    // 2. 排序：左端点升序，左端点相同时右端点降序
    intervals.sort((a, b) => {
        if (Math.abs(a.left - b.left) < eps) {
            return b.right - a.right; // 降序
        }
        return a.left - b.left; // 升序
    });
    
    let count = 0;
    let currentPos = 0;
    let i = 0;
    const n = intervals.length;
    
    // 3. 贪心选择
    while (currentPos < L - eps) {
        let maxRight = currentPos;
        const startI = i; // 记录开始位置
        
        // 扫描所有左端点不超过currentPos的区间
        while (i < n && intervals[i].left <= currentPos + eps) {
            if (intervals[i].right > maxRight) {
                maxRight = intervals[i].right;
            }
            i++;
        }
        
        // 如果maxRight没有推进，说明无法覆盖
        if (Math.abs(maxRight - currentPos) < eps) {
            return -1;
        }
        
        count++;
        currentPos = maxRight;
        
        // 提前完成检查
        if (currentPos >= L - eps) {
            break;
        }
        
        // 可选：如果i未动，说明后续区间左端点都大于currentPos，直接失败
        if (i === startI) {
            return -1;
        }
    }
    
    return count;
}

// 示例
const L = 100;
const lights = [[20, 20], [40, 10], [60, 15], [80, 20]];
const result = minLights(L, lights);
console.log(`最少需要路灯数量: ${result}`); // 输出 2

JavaScript实现要点与避坑指南：

1. 排序函数 ： Array.prototype.sort 默认按字符串Unicode码点排序，对数字排序必须传入比较函数。比较函数返回负数表示 a 在前，正数表示 b 在前。
2. 浮点数问题 ：JavaScript只有一种数字类型 Number ，是双精度浮点数，精度问题同样存在。必须使用 eps 。
3. 解构赋值 ： for (const [pos, r] of lights) 这种写法让代码更简洁易读。
4. 动态数组 ： intervals 直接使用 push 方法构建，非常方便。不需要像Java那样预先分配大小。
5. 代码风格 ：使用 const 和 let 明确变量作用域，避免使用 var 。

3.4 Python 实现：简洁高效的解题利器

Python以其极简的语法和强大的内置函数，成为算法竞赛和机试的热门选择。

def min_lights(L, lights):
    eps = 1e-9
    intervals = []
    
    # 1. 预处理
    for pos, r in lights:
        left = max(0.0, pos - r)
        right = min(L, pos + r)
        if left <= right + eps:  # 有效区间
            intervals.append((left, right))
    
    # 2. 排序：左端点升序，左端点相同则右端点降序
    # 利用Python元组比较的特性：先比较第一个元素，再比较第二个...
    # 为了右端点降序，我们存入 (left, -right)，排序后再取反
    # 或者使用key参数进行多级排序
    intervals.sort(key=lambda x: (x[0], -x[1]))
    
    count = 0
    current_pos = 0.0
    i = 0
    n = len(intervals)
    
    # 3. 贪心选择
    while current_pos < L - eps:
        max_right = current_pos
        start_i = i
        
        # 寻找能覆盖当前点且延伸最远的灯
        while i < n and intervals[i][0] <= current_pos + eps:
            if intervals[i][1] > max_right:
                max_right = intervals[i][1]
            i += 1
        
        # 如果没有进展
        if abs(max_right - current_pos) < eps:
            return -1
        
        count += 1
        current_pos = max_right
        
        if current_pos >= L - eps:
            break
        
        # 防御性判断
        if i == start_i:
            return -1
    
    return count

# 示例
if __name__ == "__main__":
    L = 100
    lights = [(20, 20), (40, 10), (60, 15), (80, 20)]
    result = min_lights(L, lights)
    print(f"最少需要路灯数量: {result}")  # 输出 2

Python实现要点与避坑指南：

1. 排序技巧 ：Python的 list.sort() 或 sorted() 的 key 参数非常强大。 key=lambda x: (x[0], -x[1]) 完美实现了“按左端点升序，左端点相同按右端点降序”。这是最简洁的实现方式。
2. 元组的使用 ：使用元组 (left, right) 来表示区间，比定义类或字典更轻量、更快。
3. 浮点数精度 ：同样需要注意 eps 。在比较时，使用 abs(a-b) < eps 。
4. 索引管理 ：Python的 while 循环和索引 i 的管理与其他语言逻辑一致。注意 i += 1 的位置。
5. 代码简洁性 ：Python代码通常是最短的，但可读性丝毫不差。 for pos, r in lights: 这种迭代方式非常Pythonic。

4. 算法复杂度分析与变体探讨

4.1 时间复杂度与空间复杂度

• 时间复杂度 ：主要消耗在排序步骤。假设有 N 个路灯，预处理是 O(N) ，排序是 O(N log N) ，贪心扫描是 O(N) （每个区间最多被访问一次）。因此，总时间复杂度为 O(N log N) 。
• 空间复杂度 ：除了存储输入，我们需要一个额外的列表来存放有效区间，空间复杂度为 O(N) 。

这是一个非常高效的算法，可以处理 N 达到 10^5 数量级的数据。

4.2 常见变体与应对策略

实际机试或面试中，题目可能会有一些变体，考察你的灵活应变能力。

1. 变体一：路灯可以安装在道路之外

   • 描述 ：路灯的 position 可以小于0或大于 L 。
   • 应对 ：我们的预处理步骤 left = max(0, pos - r) 和 right = min(L, pos + r) 已经处理了这种情况。它自动计算了路灯能照亮道路的实际区间。算法核心不变。

2. 变体二：求具体方案

   • 描述 ：不仅要求最少数目，还要求输出具体选择了哪些灯（按原输入顺序或索引）。
   • 应对 ：在预处理构建区间时，需要保留路灯的原始索引。在贪心选择记录 maxRight 时，同时记录下对应区间的索引。最后将这些索引收集起来返回。注意，如果排序打乱了顺序，输出时需要按原始索引排序，或者在一开始就建立一个 (interval, index) 的列表一起排序。

3. 变体三：道路是环形的

   • 描述 ：道路首尾相连成环。
   • 应对 ：这是一个经典难题。一种思路是破环成链：将道路长度复制一份，变成 [0, 2L] ，然后在这个双倍长度的链上，寻找一个长度为 L 的区间能被最少的灯覆盖。这需要更复杂的处理，可能用到滑动窗口或动态规划。

4. 变体四：每盏灯有开关成本，求最小总成本

   • 描述 ：每盏灯有一个打开成本 cost[i] ，目标是覆盖整条道路且总成本最小。
   • 应对 ：这就变成了一个 加权区间覆盖 问题，贪心算法可能不再适用（因为贵但照得远的灯不一定比便宜但照得近的组合更优）。这通常需要用到 动态规划(DP) 或 最短路径 模型来求解。

5. 实战调试与常见“坑点”实录

即便思路清晰，代码写出来也可能漏洞百出。下面是我在刷题和面试中总结的几个高频“坑点”。

5.1 浮点数比较陷阱

这是最普遍、最隐蔽的错误。 永远不要直接使用 == 或 > 比较浮点数！

# 错误示范
if left <= currentPos: # 可能因精度问题导致本该相等的值判断为小于或大于
    ...

# 正确示范
eps = 1e-9
if left <= currentPos + eps:
    ...
if abs(a - b) < eps: # 判断相等
    ...
if a > b + eps: # 判断大于
    ...

为什么是 1e-9 ？ 对于大多数题目， 1e-9 的精度足够。如果坐标范围很大（如 1e9 ），可能需要调整到 1e-6 。保险起见，可以使用相对误差 abs(a-b) <= max(1e-9, 1e-9 * max(abs(a), abs(b))) ，但机试中通常 1e-9 或 1e-12 的绝对误差就够了。

5.2 区间排序与选择逻辑错误

错误1：未排序或排序错误。 贪心算法的前提是区间按左端点排序。如果没排序，算法完全错误。

错误2：选择逻辑有误。 有些初学者会这样写：找到第一盏左端点 <= currentPos 的灯，选择它，然后 currentPos = this_light.right 。这是错误的！比如当前点在5，有两盏灯：A覆盖 [2, 7] ，B覆盖 [4, 12] 。错误逻辑可能先遇到A就选了A， currentPos 变成7。但实际上应该选B，直接覆盖到12。所以必须扫描所有可选区间，选右端点最大的。

错误3： i 的管理错误。 在每一轮选择后， i 不应该重置为0。因为数组已排序，之前遍历过的灯其左端点都 <= old_currentPos ，而它们的右端点都 <= maxRight （否则就会被选为新的 maxRight ）。所以对于新的 currentPos (即 maxRight) ，这些旧的灯已经没用了， i 从当前位置继续即可。重置 i 会导致算法退化为 O(N^2) 。

5.3 边界条件处理不周

1. 起点覆盖 ：如果排序后的第一个有效区间的左端点 > 0 + eps ，那么起点0就无法被覆盖，应直接返回-1。我们的算法在第一次循环时， maxRight 初始化为0，如果找不到左端点 <= 0 的灯， maxRight 不会更新，从而返回-1。这是正确的。
2. 终点覆盖 ：循环条件是 while currentPos < L 。当 currentPos >= L 时跳出。注意浮点数比较，用 currentPos >= L - eps 。
3. 空输入或全无效输入 ：如果 lights 为空，或所有灯的有效区间长度都为0，算法应返回-1。我们的预处理会得到一个空的 intervals 数组，排序后进入 while 循环， i=0, n=0 ，第一次寻找 maxRight 时 while 条件不成立， maxRight 未更新，返回-1。
4. 大数处理 ：如果 L 或坐标值很大，要注意浮点数精度和整数溢出（在其他语言如C++中，如果用整数存储，要小心加法溢出）。本题通常用浮点或双精度即可。

5.4 调试技巧与小规模测试

当你觉得代码逻辑没错但结果不对时，从小规模测试开始：

1. 最小测试 ：只有一盏灯。
   • 灯在道路内，半径足够大。应返回1。
   • 灯在道路内，半径太小，覆盖不了全长。应返回-1。
   • 灯在道路外，但光能照到道路。应返回1。
2. 两盏灯测试 ：
   • 两盏灯区间有重叠，需要两盏才能覆盖。验证计数为2。
   • 一盏灯覆盖范围很大，包含另一盏。验证计数为1（贪心应选范围大的）。
   • 两盏灯中间有缝隙。验证返回-1。
3. 特殊顺序测试 ：故意打乱输入顺序，验证排序是否起作用。
4. 浮点数测试 ：使用恰好边界的数据，如 L=10, lights=[[5,5]] ，理论上应覆盖 [0,10] 。检查 currentPos 最终是否 >= 10 - eps 。

打印中间变量 是调试的不二法门。在贪心循环中，打印出 currentPos , i , intervals[i] , maxRight 等，可以清晰看到算法的每一步决策。